302294: CF441E. Valera and Number

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Valera and Number

题意翻译

给出一个数 $x$,对它进行 $k$ 次操作,每次操作: - 以 $p \%$ 的概率对它乘以 $2$。 - 以 $(100 - p) \%$ 的概率对它加上 $1$。 求该数最终二进制下末尾 $0$ 个数的期望。

题目描述

Valera is a coder. Recently he wrote a funny program. The pseudo code for this program is given below: ```plain //input: integers x, k, p a = x; for(step = 1; step <= k; step = step + 1){ rnd = [random integer from 1 to 100]; if(rnd <= p) a = a * 2; else a = a + 1; } s = 0; while(remainder after dividing a by 2 equals 0){ a = a / 2; s = s + 1; } ``` Now Valera wonders: given the values $ x $ , $ k $ and $ p $ , what is the expected value of the resulting number $ s $ ?

输入输出格式

输入格式


The first line of the input contains three integers $ x,k,p $ ( $ 1<=x<=10^{9}; 1<=k<=200; 0<=p<=100 $ ).

输出格式


Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn't exceed $ 10^{-6} $ .

输入输出样例

输入样例 #1

1 1 50

输出样例 #1

1.0000000000000

输入样例 #2

5 3 0

输出样例 #2

3.0000000000000

输入样例 #3

5 3 25

输出样例 #3

1.9218750000000

说明

If the concept of expected value is new to you, you can read about it by the link: http://en.wikipedia.org/wiki/Expected\_value

Input

题意翻译

给出一个数 $x$,对它进行 $k$ 次操作,每次操作: - 以 $p \%$ 的概率对它乘以 $2$。 - 以 $(100 - p) \%$ 的概率对它加上 $1$。 求该数最终二进制下末尾 $0$ 个数的期望。

加入题单

上一题 下一题 算法标签: