atcoder#ABC126C. [ABC126C] Dice and Coin
[ABC126C] Dice and Coin
Score : points
Problem Statement
Snuke has a fair -sided die that shows the integers from to with equal probability and a fair coin. He will play the following game with them:
- Throw the die. The current score is the result of the die.
- As long as the score is between and (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes if the coin lands tails up.
- The game ends when the score becomes or becomes or above. Snuke wins if the score is or above, and loses if the score is .
You are given and . Find the probability that Snuke wins the game.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the probability that Snuke wins the game. The output is considered correct when the absolute or relative error is at most .
3 10
0.145833333333
- If the die shows , Snuke needs to get four consecutive heads from four coin flips to obtain a score of or above. The probability of this happening is .
- If the die shows , Snuke needs to get three consecutive heads from three coin flips to obtain a score of or above. The probability of this happening is .
- If the die shows , Snuke needs to get two consecutive heads from two coin flips to obtain a score of or above. The probability of this happening is .
Thus, the probability that Snuke wins is $\frac{1}{48} + \frac{1}{24} + \frac{1}{12} = \frac{7}{48} \simeq 0.1458333333$.
100000 5
0.999973749998