TokenDoublingGame
TCO19 SRM 752 · 2019-03-04 · by teja349
Problem Statement
You are playing a coin-flipping game.
At the beginning of the game you are given an
The game starts with N tokens on the table and 1 token in your hand.
In each round of the game, you flip the coin and act according to the outcome:
- Heads: Discard your hand (the tokens disappear). Then, take two new tokens. Place one on the table and take the other into your hand. If there are now 2*N tokens on the table, the game ends.
- Tails: Let X be the number of tokens in your hand. Take another X tokens from the table into your hand. If the table becomes empty during or after you do that, the game ends.
The expected number of coin flips during this game can be represented as a reduced fraction A/B. Let B^(-1) be the inverse element to B, modulo 10^9 + 7. Compute and return the value (A * B^(-1)) modulo 10^9 + 7.
Notes
- For each valid input the value B^(-1) exists.
Constraints
- N will be between 1 and 100,000, inclusive.
100000 Returns: 386506648
99999 Returns: 662623410
1 Returns: 1
The game ends after the first coin flip, regardless of its outcome.
2 Returns: 333333339
The exact answer as a reduced fraction is 10/3. Computing modulo 10^9 + 7, we have 10 * 3^(-1) = 10 * 333,333,336 = 333,333,339.
3 Returns: 86956528
13 Returns: 444154848
Here, the exact answer is 2795844533351/105312396244, which means that the return value is (2795844533351 * 105312396244^(-1)) mod (10^9 + 7).
Submissions are judged against all 48 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TokenDoublingGame with a public method int expectation(int N) · 48 test cases · 2 s / 256 MB per case