Many thanks to Clive Fraser who created this puzzle as an advanced sequel to more simple Fibonacci Guessing Game!
After some time playing the Fibonacci Guessing Game (See previous problem for details) Alice had to agree with Bob, that using a binary split to halve the range at each step is actually a better strategy.
Using this strategy a range of even length will be split into two equal parts. A range of odd length will be split into two parts with lengths differing by one.
For example, if the target is in the range 1 .. 21 Alice will split this range into sub-ranges of 10 and 11.
She will decide randomly whether to choose sub-ranges of 1 .. 10 and 11 .. 21 or sub-ranges of 1 .. 11 and
12 .. 21. The first option is selected by the question "is your number above 10?" and the second by the
question "is your number above 11?". Bob's answer determines which of the two ranges contains the secret
number. The game continues until the secret number lies in a range of length 1, at which point it is known and
the game ends.
You are asked to find the expectation number of guesses needed when Alice applies the binary split strategy.
Input data: The first line gives the number N of guessing ranges. The next N lines each contain the
maximum number M for the initial guessing range 1 .. M.
Answer: For each range you should give the expected number of guessing steps, rounded to 4 digits after
the decimal point, including any trailing zeros. Combine all of your answers into a single string, separated by spaces.
Example:
input data:
4
21
377
2584
75025
answer:
4.4762 8.6419 11.4149 16.2530