Love is... a kind of guessing game after all
Alice and Bob were playing the typical number-guessing game. You know it - say A thinks of the number in
range 1 .. 1000 and B starts asking is your number above 500, if yes, next guess is ...above 750,
otherwise ...above 250 and so on - so that at every step the range is effectively halved. The value
in the said range could be guessed with 10 attempts at most.
However, Alice is bored at this "halving" approach and decided to use instead fibonacci numbers. Let's demonstrate
the idea. Say, the target value is in range 1 .. 13. The game flow is like this:
- is your number above
8?
If yes, the remaining range is 5 values long (9 .. 13), so she split it into parts of size 2 and 3,
asking, for example, is the number above 10 (she can also ask "above 11" actually).
If on the other hand the first guess threw her into the lower subrange (1 .. 8) she is to split into
parts of 3 and 5 respectively.
Bob laughs at this fancy, arguing that Alice will need significantly more steps to get to the secret number.
Because, for example, range up to 4000 needs only 12 divisions, but there are 17 fibonacci values below
that. Is it actually as bad as that?
Input data contain the number N of guessing ranges to follow. Next N lines follow, each of them describing
the range of numbers to guess form - actually single fibonacci value F for range 1 .. F.
Answer should give for each of these ranges the expected average number of guessing steps, rounded to 2
digits after decimal point. Keep trailing zeroes.
Example
input data
4
21
377
2584
75025
4.57 8.91 11.81 16.87
P.S. when splitting every new fibonaccian subrange into two uneven parts Alice will randomly choose which part is larger (upper or lower) so that Bob can't exploit this unevennes.