Connection Status:
Competition Arena > JanuszInTheCasino

JanuszInTheCasino

SRM 645 · 2014-12-30 · by w10d

SRM 645 · 2014-12-30 · by w10d · Math, Recursion
Class Name: JanuszInTheCasino
Return Type: double
Method Name: findProbability
Arg Types: (long long, int, int)
Problem Statement

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:

  1. Each player places their token onto one of the fields.
  2. One of the fields is chosen uniformly at random.
  3. The tokens in the chosen field are removed from the game. The players who placed those tokens are out of the game.
The players who are still in the game after the last round win the game.

Our group of players wants to maximize the probability that at least one of them wins the game. You are given the long n and the ints m and k. Compute and return the probability that there will be at least one winner if they play the game optimally.

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
0)
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)
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.

2)
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.

3)
5
4
5
Returns: 0.87109375
4)
1000000000000
2
40
Returns: 0.9094947017729282
36)
1011100000
3
50
Returns: 0.9989955665603316

0.999 - eps

37)
77
5
50
Returns: 0.0010989371304622444

0.001 + eps

Submissions are judged against all 48 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class JanuszInTheCasino with a public method double findProbability(long long n, int m, int k) · 48 test cases · 2 s / 256 MB per case

Submitting as anonymous