Problem Statement
Two players are going to play a number guessing game.
Genevieve will generate an integer between 0 and N-1 uniformly at random. Then, Adam will attempt to guess the number.
In each guess Adam announces an integer X and receives the correct one of the answers "less than X", "correct", and "greater than X". Once he receives the message "correct", the game ends.
The payoff for the game is determined by a single real number P. If Adam guesses correctly in guess number i, Genevieve will give him P-i dollars. (Guesses are numbered starting from 1. If i is greater than P, this value will be negative and thus Adam actually loses money.)
Determine and return the real number P for which the game is fair: Adam's expected profit from playing the game should be exactly zero, assuming he plays the game optimally.
Definition
- Class:
- GuessForMoney
- Method:
- balance
- Parameters:
- long
- Returns:
- double
- Method signature:
- double balance(long N)
- (be sure your method is public)
Notes
- Your return value must have an absolute or a relative error at most 1e-9 in order to be accepted.
Constraints
- N will be between 1 and 10^12, inclusive.
Examples
2
Returns: 1.5
Adam will either get lucky and guess the correct number in his first guess, or he will get unlucky and he will guess it in the second guess. If we set P = 1.5, the game will be fair: Adam either gains or loses 0.5, each with 50 percent probability.7
Returns: 2.4285714285714284
Adam should follow the obvious strategy: In the first round, guess 3. If there is a second round, guess 1 if 3 was too large, or 5 if 3 was too small. If there is a third round, guess the correct value among 0, 2, 4, 6.12
Returns: 3.0833333333333335
1
Returns: 1.0
Even though Adam knows what the answer is already before the game starts, in order to win the game he must actually make a guess and get the answer "correct".