GuessForMoney
SRM 812 · 2021-08-31 · by misof
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.
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.
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
1000000000000 Returns: 38.900488372265
987654321987 Returns: 38.88674447804475
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".
Submissions are judged against all 56 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GuessForMoney with a public method double balance(long long N) · 56 test cases · 2 s / 256 MB per case