fork 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, 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
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/aoqfdZ
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!