This problem was originally published on CodeAbbey.com around June 21st, 2024
Let's imagine a number line of sequential integer values labeled 0 to n. We take a stone
and place it on 0, so the stone's position is p = 0. We then use a random number generator
to obtain a random value r in the range [1, n - p], and then we reposition the stone to
the new value p + r, repeating the process until the stone is positioned at n.
For a number line of length n, the minimum possible amount of moves it could take to reach
the end would be 1, if the first roll yielded n. The maximum amount of moves it could take
would be n, if each roll only yielded 1.
What is the expected value of moves required to reach the end of a number line of length n?
Problem Statement
Input data gives the number of testcases T in the first line.
The second line will consist of T integer values of n separated by spaces.
Answer should contain T space-separated decimal values corresponding to the expected
values of turns required to reach the end of a number line of length n.
Error should be less than 1e-6.
Example:
input data:
3
2 4 10
answer:
1.5 2.083333 2.928968