Advertisement
Guest User

Untitled

a guest
Apr 20th, 2014
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.03 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<cmath>
  5. #include<algorithm>
  6. #include<cstring>
  7. #include<iomanip>
  8.  
  9. using namespace std;
  10.  
  11. struct matrix
  12. {
  13.     double a[2][2];
  14.     matrix mul(matrix& m)
  15.     {
  16.         matrix res;
  17.         for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) res.a[i][j] = 0.0;
  18.         for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++)
  19.         {
  20.             res.a[i][j] += a[i][k] * m.a[k][j];
  21.         }
  22.         return res;
  23.     }
  24.     void id()
  25.     {
  26.         a[0][0] = 1.0;
  27.         a[0][1] = 0.0;
  28.         a[1][0] = 0.0;
  29.         a[1][1] = 1.0;
  30.     }
  31. };
  32.  
  33. int n, T[100005];
  34. double P[100005];
  35. char pos[100005];
  36.  
  37. matrix do_pow(double p, int t)
  38. {
  39.     vector<matrix> pows(30);
  40.     pows[0].a[0][0] = 1.0 - p;
  41.     pows[0].a[0][1] = p;
  42.     pows[0].a[1][0] = p;
  43.     pows[0].a[1][1] = 1.0 - p;
  44.     matrix res;
  45.     res.id();
  46.     if(t & 1)
  47.     {
  48.         res = pows[0];
  49.     }
  50.     for(int i = 1; i < 30; i++)
  51.     {
  52.         pows[i] = pows[i-1].mul(pows[i-1]);
  53.         if((t>>i)&1)
  54.         {
  55.             res = res.mul(pows[i]);
  56.         }
  57.     }
  58.     return res;
  59. }
  60.  
  61. double solve()
  62. {
  63.     cout << endl;
  64.     double pl = 1.0, evl = 0.0, pr = 0.0, evr = 0.0;
  65.     for(int i = n-1; i >= 0; i--)
  66.     {
  67.         matrix m = do_pow(P[i], T[i]);
  68.         double pli = (pos[i] == 'L' ? m.a[0][0] : m.a[1][0]);
  69.         double pri = (pos[i] == 'L' ? m.a[0][1] : m.a[1][1]);
  70.         cout << pli << " " << pri << endl;
  71.         double plnew = pri;
  72.         double prnew = pli;
  73.         //double evlnew = pr * 1.0 + evr;
  74.         //double evrnew = pl * 1.0 + evl;
  75.         double evlnew = pr * (1.0 + evr) + pl * evl;
  76.         double evrnew = pl * (1.0 + evl) + pr * evr;
  77.         pr = prnew;
  78.         pl = plnew;
  79.         evr = evrnew;
  80.         evl = evlnew;
  81.         cout << pl << " " << pr << " " << evl << " " << evr << endl;       
  82.     }
  83.     return pl * evl + pr * evr;
  84. }
  85.  
  86. int main()
  87. {
  88.     while(cin >> n)
  89.     {
  90.         for(int i = 0; i < n; i++) scanf(" %d %c %lf ", &T[i], &pos[i], &P[i]);
  91.         cout << fixed << setprecision(15) << solve() << endl;
  92.     }
  93. }
  94.  
  95.  
  96.  
  97. 2
  98. 5 L 0.5
  99. 1 R 0.4
  100.  
  101. 1
  102. 2 L 0.2
  103.  
  104. 4
  105. 3 L 0
  106. 4 R 0
  107. 5 L 1
  108. 6 R 1
  109.  
  110. 1
  111. 3 L 1
  112.  
  113. 2
  114. 1 L 0.4
  115. 2 R 0.4
  116.  
  117.  
  118.  
  119.  
  120. 0.4 0.6
  121. 0.6 0.4 0 1
  122. 0.5 0.5
  123. 0.5 0.5 1.4 0.6
  124. 1.000000000000000
  125.  
  126. 0.680000000000000 0.320000000000000
  127. 0.320000000000000 0.680000000000000 0.000000000000000 1.000000000000000
  128. 0.680000000000000
  129.  
  130. 0.000000000000000 1.000000000000000
  131. 1.000000000000000 0.000000000000000 0.000000000000000 1.000000000000000
  132. 0.000000000000000 1.000000000000000
  133. 1.000000000000000 0.000000000000000 1.000000000000000 1.000000000000000
  134. 0.000000000000000 1.000000000000000
  135. 1.000000000000000 0.000000000000000 1.000000000000000 2.000000000000000
  136. 1.000000000000000 0.000000000000000
  137. 0.000000000000000 1.000000000000000 2.000000000000000 2.000000000000000
  138. 2.000000000000000
  139.  
  140. 0.000000000000000 1.000000000000000
  141. 1.000000000000000 0.000000000000000 0.000000000000000 1.000000000000000
  142. 0.000000000000000
  143.  
  144. 0.480000000000000 0.520000000000000
  145. 0.520000000000000 0.480000000000000 0.000000000000000 1.000000000000000
  146. 0.600000000000000 0.400000000000000
  147. 0.400000000000000 0.600000000000000 1.480000000000000 0.520000000000000
  148. 0.904000000000000
  149. unusual@unusual-Neo:~/Desktop/ACM$ g++ -Wall -Wextra -o E E.cpp && E < E.in
  150.  
  151. 0.4 0.6
  152. 0.6 0.4 0 1
  153. 0.5 0.5
  154. 0.5 0.5 0.8 1
  155. 0.900000000000000
  156.  
  157. 0.680000000000000 0.320000000000000
  158. 0.320000000000000 0.680000000000000 0.000000000000000 1.000000000000000
  159. 0.680000000000000
  160.  
  161. 0.000000000000000 1.000000000000000
  162. 1.000000000000000 0.000000000000000 0.000000000000000 1.000000000000000
  163. 0.000000000000000 1.000000000000000
  164. 1.000000000000000 0.000000000000000 0.000000000000000 1.000000000000000
  165. 0.000000000000000 1.000000000000000
  166. 1.000000000000000 0.000000000000000 0.000000000000000 1.000000000000000
  167. 1.000000000000000 0.000000000000000
  168. 0.000000000000000 1.000000000000000 0.000000000000000 1.000000000000000
  169. 1.000000000000000
  170.  
  171. 0.000000000000000 1.000000000000000
  172. 1.000000000000000 0.000000000000000 0.000000000000000 1.000000000000000
  173. 0.000000000000000
  174.  
  175. 0.480000000000000 0.520000000000000
  176. 0.520000000000000 0.480000000000000 0.000000000000000 1.000000000000000
  177. 0.600000000000000 0.400000000000000
  178. 0.400000000000000 0.600000000000000 0.960000000000000 1.000000000000000
  179. 0.984000000000000
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement