fork download
  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, 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. map<long int,int> index;
  51. for(i=0;i<8;i++)
  52. index[ar[i]]=i; //edited
  53.  
  54.  
  55. // Calculating my answer
  56. // h[i][j] represents probabilty of number i upto jth machine
  57. h[1][0]=1.00000000;
  58. for(j=0; j<n; j++)
  59. {
  60. for(m=0; m<8; m++)
  61. {
  62. h[index[ar[m]&k]][j+1]+=a*h[m][j]; //edited
  63. h[index[ar[m]|k]][j+1]+=b*h[m][j]; //edited
  64. h[index[ar[m]^k]][j+1]+=c*h[m][j]; //edited
  65. }
  66. }
  67.  
  68. // g stores my answer
  69. for(j=0; j<8; j++)
  70. {
  71. g+=ar[j]*h[j][n];
  72. }
  73.  
  74. // Calculating correct answer (someone else's code for reference)
  75. m1[x]=1.00000000;
  76. for(int i=1;i<=n;i++)
  77. {
  78. m2.clear();
  79. for(it=m1.begin();it!=m1.end();it++)
  80. {
  81. uint j=it->first;
  82. double ab=it->second;
  83. uint p=j&k;
  84. m2[p]+=(double)(a*ab);
  85. p=j|k;
  86. m2[p]+=(double)(b*ab);
  87. p=j^k;
  88. m2[p]+=(double)(c*ab);
  89. }
  90. m1.clear();
  91. m1=m2;
  92. }
  93.  
  94. double ans=0;
  95. for(it=m1.begin(); it!=m1.end(); it++)
  96. {
  97. ans+=it->first*it->second;
  98. }
  99.  
  100. /** DEBUG Output START **/
  101. printf("**DEBUG Output Start**\nNum => %6s %8s\n", "myProb", "correctProb");
  102. for(j=0; j<8; j++)
  103. {
  104. printf("%u => %.9lf, %.9lf\n", ar[j], m1[ar[j]], h[j][n]);
  105. }
  106. // There are only 8 possible numbers as can be seen from the output
  107. printf("Total numbers=%u ", m1.size());
  108. printf("\n**DEBUG Output END**\n");
  109. /** DEBUG Output END **/
  110.  
  111. printf("my-ans=%.9lf, correct-ans=%.9lf\n\n", g, ans);
  112. m1.clear();
  113. m2.clear();
  114. for(j=0; j<=n; j++)
  115. {
  116. for(k=0; k<8; k++) h[k][j]=0;
  117. }
  118. g=0;
  119. }
  120.  
  121. return 0;
  122. }
Success #stdin #stdout 0s 9720KB
stdin
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
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