Valera and Number

Time Limit: 20 Sec  Memory Limit: 512 MB

Description

　　

Input

　　

Output

　　

Sample Input

　　5 3 25

Sample Output

　　1.9218750000

HINT

　　

Solution

　　考虑运用DP。

　　

Code

1 #include
      
          2 #include
       
           3 #include
        
            4 #include
         
             5 #include
          
              6 #include
           
             7 #include
            
              8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 800005;12 const int MOD = 1e9 + 7;13 const int all = 255;14 15 int x, n;16 double p;17 double f[205][260][255][2];18 double Ans;19 int val, num;20 21 int get() 22 { 23 int res;char c; 24 while( (c=getchar())<48 || c>57 );25 res=c-48; 26 while( (c=getchar())>=48 && c<=57 ) 27 res=res*10+c-48; 28 return res; 29 } 30 31 void Deal_first(int n)32 {33 int record[250], num = 0, x = n;34 while(x)35 record[++num] = x & 1,36 x >>= 1;37 int j = 1, pos = 9, val = record[pos];38 for(pos = 9; pos + j - 1 <= num; j++)39 if(record[pos + j] != val) break;40 41 f[0][n & all][j][val] = 1; 42 }43 44 int Get(int x)45 {46 int res = 0;47 while(x % 2 == 0) res++, x >>= 1;48 return res;49 }50 51 int main()52 {53 x = get(), n = get(), p = (double)get() / 100;54 Deal_first(x);55 56 for(int i = 0; i < n; i++)57 for(int s = 0; s <= all; s++)58 for(int j = 1; j <= 250; j++)59 for(int k = 0; k <= 1; k++)60 {61 val = s >> 8 - 1 & 1;62 if(val != k) num = 1; else num = j + 1;63 f[i + 1][s << 1 & all][num][val] += f[i][s][j][k] * p;64 65 val = s == all ? (k ^ 1) : k;66 if(val != k && k == 0) num = 1; else num = j;67 f[i + 1][s + 1 & all][num][val] += f[i][s][j][k] * (1 - p);68 }69 70 for(int s = 0; s <= all; s++)71 for(int j = 1; j <= 250; j++)72 for(int k = 0; k <= 1; k++)73 {74 if(s == 0 && k == 0) val = j + 8;75 else if(s == 0 && k == 1) val = 8;76 else val = Get(s);77 Ans += f[n][s][j][k] * val;78 }79 80 printf("%.8lf", Ans);81 }
            
           
          
         
        
       
      

 

• Unkonwn