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
1000000000000
Returns: 38.900488372265
987654321987
Returns: 38.88674447804475
4718803
Returns: 21.222306801110367
255999072
Returns: 26.95142031217988
104554406420
Returns: 35.68547909036085
5955217264
Returns: 31.557578308699636
550195858414
Returns: 38.0015995923625
128654
Returns: 15.981345313787367
23311791531
Returns: 33.526079032308246
56300
Returns: 14.836252220248667
398384431
Returns: 27.652379861701974
6
Returns: 2.3333333333333335
7062484
Returns: 21.8122332029354
48086382200
Returns: 34.570916056583684
5
Returns: 2.2
2507971
Returns: 20.327619816975556
14823990
Returns: 22.868240534431013
5380883297
Returns: 31.403619985070268
27356
Returns: 13.802748939903495
15909
Returns: 12.97108554906028
234
Returns: 6.944444444444445
433243449084
Returns: 37.73106952912885
49911
Returns: 14.687283364388612
4530769
Returns: 21.148529752896252
1744200488
Returns: 29.768786254347155
123607717077
Returns: 35.888103779569164
94494
Returns: 15.61309712785997
390160982005
Returns: 37.59095132726277
33064496
Returns: 23.985183200735918
85092
Returns: 15.459855215531425
276590639
Returns: 27.058969443286184
1193
Returns: 9.293378038558256
24
Returns: 3.9166666666666665
6643732625
Returns: 31.70706197210939
232351988
Returns: 26.844703549512992
6
Returns: 2.3333333333333335
391885784965
Returns: 37.59715295900029
7815141
Returns: 21.92662410057605
2771
Returns: 10.526524720317575
1500396267
Returns: 29.56872236806225
306
Returns: 7.359477124183006
432
Returns: 7.837962962962963
10275110721
Returns: 32.328011287130145
247443
Returns: 16.940665122876783
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".
76123533
Returns: 25.2368435264296
8736258
Returns: 22.07959071263692
71002
Returns: 15.154221007858933
348
Returns: 7.557471264367816
7883720804
Returns: 31.91042126280757
8148
Returns: 11.996318114874816
11026628440
Returns: 32.44196535301048
999999999999
Returns: 38.9004883722639