Problem Statement
Janusz is in a casino with some friends. Their group consists of n people. They are all going to play a game.
The game is played on a plan that is divided into m fields. At the beginning of the game, each player gets their own unique token. The game then consists of k rounds. Each round looks as follows:
- Each player places their token onto one of the fields.
- One of the fields is chosen uniformly at random.
- The tokens in the chosen field are removed from the game. The players who placed those tokens are out of the game.
Our group of players wants to maximize the probability that at least one of them wins the game.
You are given the
Definition
- Class:
- JanuszInTheCasino
- Method:
- findProbability
- Parameters:
- long, int, int
- Returns:
- double
- Method signature:
- double findProbability(long n, int m, int k)
- (be sure your method is public)
Notes
- The return value must have an absolute error at most 1e-3.
Constraints
- n will be between 1 and 10^12, inclusive.
- m and k will be between 1 and 50, inclusive.
Examples
3
2
2
Returns: 0.75
There are 3 players, 2 fields on the plan, and 2 rounds of the game. In the first round the players should place one token onto the first field and two tokens onto the second field. With probability 0.5 the first field is chosen. If that happens, there will be two players in the second round. Each of them will choose a different field and thus one of them will certainly win the game. With probability 0.5 the second field is chosen in the first round. If that happens, there will only be a single player in the second round. The probability that this player survives the second round is 0.5. Hence, the answer is 0.5*1 + 0.5*0.5 = 0.75.
1
3
3
Returns: 0.2962962962962962
There is only one player: Janusz. He will survive each round with probability 2/3. Hence, the probability that he will win the entire game is (2/3)^3.
4
3
2
Returns: 1.0
One optimal strategy for the first round is to put two tokens onto one field and one token onto each of the other two fields. Even if we lose the two tokens, we will still have two players in the second round and we can make sure that at least one of them will win the game.
5
4
5
Returns: 0.87109375
1000000000000
2
40
Returns: 0.9094947017729282
2
10
50
Returns: 0.010293277937713185
4324
3
25
Returns: 0.16981540046618473
7
4
5
Returns: 0.982421875
8
4
5
Returns: 1.0
1073741824
2
30
Returns: 1.0
1073640803
2
30
Returns: 0.9999059168621898
21
21
42
Returns: 0.9699964585463249
23323233
3
45
Returns: 0.2724504209732145
534545
4
50
Returns: 0.2901849427392484
432545123543
2
45
Returns: 0.012293671817445784
323432541
3
50
Returns: 0.4806697202565555
10
41
47
Returns: 0.9827463407427732
10
5
50
Returns: 1.4272436512995996E-4
45
17
30
Returns: 0.9999999972560882
564656
3
35
Returns: 0.37472411790163795
9
28
43
Returns: 0.8970519842195317
5
14
47
Returns: 0.146546252339407
3
50
50
Returns: 0.7481823862559633
45
8
29
Returns: 0.6868117579367694
2323
2
15
Returns: 0.070892333984375
1000
6
45
Returns: 0.25763800991541025
7
41
43
Returns: 0.9566256685135859
10
26
35
Returns: 0.9611832973858667
23
4
27
Returns: 0.009732852154560212
4
15
3
Returns: 1.0
32300032
5
40
Returns: 1.0
232876324
3
48
Returns: 0.7231326905540486
34254312343
3
45
Returns: 1.0
455666434444
47
49
Returns: 0.9999999999999861
455000654666
42
50
Returns: 1.0000000000000016
1072240003
2
30
Returns: 0.9986013201996684
1011100000
3
50
Returns: 0.9989955665603316
0.999 - eps
77
5
50
Returns: 0.0010989371304622444
0.001 + eps
100000000000
50
50
Returns: 0.9999999999999993
100000000
3
40
Returns: 1.0
1000000000000
50
50
Returns: 0.9999999999999949
10
5
1
Returns: 1.0
100000000000
21
50
Returns: 0.9999999999999998
1000000000
50
50
Returns: 1.0
1000000000000
10
50
Returns: 0.9999999999999993
1000000000000
50
49
Returns: 0.9999999999999951
99999999999
50
50
Returns: 0.9999999999999993
10000000000
50
50
Returns: 1.000000000000024