- At the beginning of the game, you are given N as input.
- Set V=N, and set X=1
- Flip a fair coin.
3a. If the coin lands on heads: Increase V by X, and then set X=1
3b. If the coin lands on tails: Decrease V by X, and then set X=2X - If V less than or equal to 0 or V greater than or equal to 2N
4a. End the game. - Proceed to step 3.
Given the initial value N, what is the expected number of turns (coin flips) you will play before ending the game?
constraints-Input:
Input consists of a single integer, N (with 1≤N≤1,000,000), the initial input to the game.
Output:
A single decimal number, containing the expected number of turns you will play this game before it ends. Your output will be accepted if it is within 10−6 absolute or relative error.
Sample Input 1:
1
Sample Output 1:
1.000000000000
Sample Input 2:
3
Sample Output 2:
3.9609375