fork(4) download
copy 
  1. // https://code.google.com/codejam/contest/8264486/dashboard#s=p2
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. #define uint unsigned int
  6. #define ll long long
  7. #define rep(i, n) for(i=0; i<n; i++)
  8.  
  9. using namespace std;
  10.  
  11. uint k;
  12. double a, b, c, g;
  13. map<uint,double> m1,m2;
  14. map<uint,double>::const_iterator it;
  15.  
  16. double h[8][100001];
  17.  
  18. // Transition table tr[8][3]
  19. // tr[i][0] => position of (ar[i] AND k) in ar[]
  20. // tr[i][1] => position of (ar[i] OR k) in ar[]
  21. // tr[i][2] => position of (ar[i] XOR k) in ar[]
  22. int tr[8][3]={
  23.     {0, 7, 7},
  24.     {2, 3, 6},
  25.     {2, 7, 4},
  26.     {7, 3, 5},
  27.     {4, 7, 2},
  28.     {0, 3, 3}, /** GREATEST ERROR tr[5][2] should have been 3 instead of 7 **/
  29.     {4, 3, 1},
  30.     {7, 7, 0}
  31. };
  32.  
  33. int main()
  34. {
  35.     //freopen("in.txt","r",stdin);
  36.     //freopen("to1.txt","w",stdout);
  37.     int t, tc, n, i, j, ia, ib, ic;
  38.     uint x, m;
  39.  
  40.     scanf("%d",&t);
  41.     rep(tc, t)
  42.     {
  43.         printf("Case #%d:\n",tc+1);
  44.         scanf("%d%u%u%d%d%d", &n, &x, &k, &ia, &ib, &ic);
  45.         a=.01*ia; b=.01*ib; c=.01*ic;
  46.  
  47.         // Array of all 8 possible numbers
  48.         uint ar[8] = {0, x, x&k, x|k, (~x)&k, x&(~k), x^k, k};
  49.  
  50.         // Calculating my answer
  51.         // h[i][j] represents probabilty of number i upto jth machine
  52.         h[1][0]=1.00000000;
  53.         for(j=0; j<n; j++)
  54.         {
  55.             for(m=0; m<8; m++)
  56.             {
  57.                 h[tr[m][0]][j+1]+=a*h[m][j];
  58.                 h[tr[m][1]][j+1]+=b*h[m][j];
  59.                 h[tr[m][2]][j+1]+=c*h[m][j];
  60.             }
  61.         }
  62.  
  63.         // g stores my answer
  64.         for(j=0; j<8; j++)
  65.         {
  66.             g+=ar[j]*h[j][n];
  67.         }
  68.  
  69. 		// Calculating correct answer (someone else's code for reference)
  70.         m1[x]=1.00000000;
  71.         for(int i=1;i<=n;i++)
  72.         {
  73.             m2.clear();
  74.             for(it=m1.begin();it!=m1.end();it++)
  75.             {
  76.                 uint j=it->first;
  77.                 double ab=it->second;
  78.                 uint p=j&k;
  79.                 m2[p]+=(double)(a*ab);
  80.                 p=j|k;
  81.                 m2[p]+=(double)(b*ab);
  82.                 p=j^k;
  83.                 m2[p]+=(double)(c*ab);
  84.             }
  85.             m1.clear();
  86.             m1=m2;
  87.         }
  88.  
  89. 		double ans=0;
  90.         for(it=m1.begin(); it!=m1.end(); it++)
  91.         {
  92.             ans+=it->first*it->second;
  93.         }
  94.  
  95. 		/** DEBUG Output START **/
  96. 		printf("**DEBUG Output Start**\nNum => %6s %8s\n", "myProb", "correctProb");
  97.         for(j=0; j<8; j++)
  98.         {
  99.             printf("%u => %.9lf, %.9lf\n", ar[j], m1[ar[j]], h[j][n]);
  100.         }
  101.         // There are only 8 possible numbers as can be seen from the output
  102.         printf("Total numbers=%u ", m1.size());
  103.         printf("\n**DEBUG Output END**\n");
  104.         /** DEBUG Output END **/
  105.  
  106.         printf("my-ans=%.9lf, correct-ans=%.9lf\n\n", g, ans);
  107.         m1.clear();
  108.         m2.clear();
  109.         for(j=0; j<=n; j++)
  110.         {
  111.             for(k=0; k<8; k++) h[k][j]=0;
  112.         }
  113.         g=0;
  114.     }
  115.  
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 9712KB
comments (?)
stdin
copy 
4
6 4229 4808 66 21 13
7 1230 6598 35 29 36
8 5978 3308 71 29 0
9 7081 5231 78 9 13
8 7552 3703 52 18 30
5 2822 2887 32 66 2
10 8191 0 10 30 60
1 9216 8704 1 98 1
10 0 8191 10 80 10
9 9888 5834 55 16 29
5 8191 0 10 30 60
5 8525 2059 1 78 21
7 4188 6772 65 23 12
1 8191 0 10 30 60
9 5973 7383 53 1 46
5 6973 7672 19 27 54
10 9216 8704 33 33 34
5 9216 8704 1 1 98
5 5945 2829 46 39 15
8 7608 3150 66 28 6
10 9216 8704 98 1 1
5 0 8191 10 80 10
8 6738 4672 77 8 15
10 9216 8704 1 98 1
8 4951 5554 89 2 9
9 4646 1476 41 8 51
3 7840 4046 22 33 45
9 2710 7061 100 0 0
6 4769 9477 28 0 72
4 9310 9540 22 33 45
5 9356 2372 45 47 8
5 5871 8306 59 14 27
1 1667 696 22 33 45
9 5117 1495 29 39 32
7 8082 5967 27 27 46
5 9216 8704 98 1 1
1 0 8191 10 80 10
1 9216 8704 98 1 1
9 6783 6427 58 12 30
9 3704 1603 68 22 10
1 9216 8704 1 1 98
9 2474 6792 40 28 32
2 991 5210 22 33 45
5 9216 8704 1 98 1
7 6222 7971 78 5 17
9 5590 2749 32 18 50
10 9216 8704 1 1 98
8 3364 2148 78 3 19
5 4633 7402 33 66 1
9 8078 5492 51 16 33
stdout
copy 
Case #1:
**DEBUG Output Start**
Num => myProb correctProb
0 => 0.159577678, 0.159577678
4229 => 0.000004827, 0.000004827
4224 => 0.132621082, 0.132621082
4813 => 0.001114026, 0.001114026
584 => 0.110461547, 0.110461547
5 => 0.000425951, 0.000425951
589 => 0.000000000, 0.000000000
4808 => 0.595794889, 0.595794889
Total numbers=8 
**DEBUG Output END**
my-ans=3494.667167506, correct-ans=3494.667167506

Case #2:
**DEBUG Output Start**
Num => myProb correctProb
0 => 0.293991079, 0.293991079
1230 => 0.000000000, 0.000000000
198 => 0.045475601, 0.045475601
7630 => 0.031269674, 0.031269674
6400 => 0.044691959, 0.044691959
1032 => 0.016968964, 0.016968964
7432 => 0.000783642, 0.000783642
6598 => 0.566819082, 0.566819082
Total numbers=8 
**DEBUG Output END**
my-ans=4296.828615594, correct-ans=4296.828615594

Case #3:
**DEBUG Output Start**
Num => myProb correctProb
0 => 0.000000000, 0.000000000
5978 => 0.000000000, 0.000000000
1096 => 0.064575353, 0.064575353
8190 => 0.000050025, 0.000050025
2212 => 0.000000000, 0.000000000
4882 => 0.000000000, 0.000000000
7094 => 0.000000000, 0.000000000
3308 => 0.935374622, 0.935374622
Total numbers=8 
**DEBUG Output END**
my-ans=3165.403539187, correct-ans=3165.403539187

Case #4:
**DEBUG Output Start**
Num => myProb correctProb
0 => 0.160126190, 0.160126190
7081 => 0.000000000, 0.000000000
4137 => 0.224320856, 0.224320856
8175 => 0.000000755, 0.000000755
1094 => 0.203608933, 0.203608933
2944 => 0.000000442, 0.000000442
4038 => 0.000000011, 0.000000011
5231 => 0.411942813, 0.411942813
Total numbers=8 
**DEBUG Output END**
my-ans=3305.643927519, correct-ans=3305.643927519
https://ideone.com/y1dsQj
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!