Valera and Number

Time Limit: 20 Sec Memory Limit: 512 MB

Description

img

Input

img

Output

img

Sample Input

5 3 25

Sample Output

1.9218750000

HINT

img

Solution

考虑运用DP。

img

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 800005;
const int MOD = 1e9 + 7;
const int all = 255;

int x, n;
double p;
double f[205][260][255][2];
double Ans;
int val, num;

int get()
{
int res;char c;
while( (c=getchar())<48 || c>57 );
res=c-48;
while( (c=getchar())>=48 && c<=57 )
res=res*10+c-48;
return res;
}

void Deal_first(int n)
{
int record[250], num = 0, x = n;
while(x)
record[++num] = x & 1,
x >>= 1;
int j = 1, pos = 9, val = record[pos];
for(pos = 9; pos + j - 1 <= num; j++)
if(record[pos + j] != val) break;

f[0][n & all][j][val] = 1;
}

int Get(int x)
{
int res = 0;
while(x % 2 == 0) res++, x >>= 1;
return res;
}

int main()
{
x = get(), n = get(), p = (double)get() / 100;
Deal_first(x);

for(int i = 0; i < n; i++)
for(int s = 0; s <= all; s++)
for(int j = 1; j <= 250; j++)
for(int k = 0; k <= 1; k++)
{
val = s >> 8 - 1 & 1;
if(val != k) num = 1; else num = j + 1;
f[i + 1][s << 1 & all][num][val] += f[i][s][j][k] * p;

val = s == all ? (k ^ 1) : k;
if(val != k && k == 0) num = 1; else num = j;
f[i + 1][s + 1 & all][num][val] += f[i][s][j][k] * (1 - p);
}

for(int s = 0; s <= all; s++)
for(int j = 1; j <= 250; j++)
for(int k = 0; k <= 1; k++)
{
if(s == 0 && k == 0) val = j + 8;
else if(s == 0 && k == 1) val = 8;
else val = Get(s);
Ans += f[n][s][j][k] * val;
}

printf("%.8lf", Ans);
}