PStepsGame | Topcoder Archive

Problem Statement

This problem is about a game that is essentially isomorphic to game played in a currently popular TV show. Context has been altered to prevent too large spoilers.

There is a group of N players. The players will play an individual game.

Games are played sequentially: the next player can begin only after the previous player's game has ended.

Each player can observe all previous players. We'll assume that everyone has a perfect memory.

In the game, there are P pairs of bottles. In each pair, one bottle contains water and one contains vinegar.

The player must repeatedly select a bottle and drink a gulp from that bottle. Drinking vinegar immediately eliminates the player from the game.

Once the player has successfully taken P gulps of water from P different bottles (i.e., all available bottles of water), that player wins the game.

Given N and P, calculate and return the expected number of players who will win the game.

Definition

Class:: PStepsGame
Method:: solve
Parameters:: int, int
Returns:: double
Method signature:: double solve(int N, int P)
(be sure your method is public)

Notes

The return value must have an absolute or a relative error at most 1e-9.

Constraints

N will be between 1 and 5,000, inclusive.
P will be between 1 and 5,000, inclusive.

Examples

```
20
```
```
1
```
```
Returns: 19.5
```
Twenty contestants, one pair of bottles. The first contestant will either be lucky and find water, or unlucky and find vinegar. All the following contestants will learn which bottle contains water and they will be able to win.
```
1
```
```
15
```
```
Returns: 3.0517578125E-5
```
One player, 15 pairs of bottles. The player has a 1 in 2^15 probability of winning.
```
2
```
```
5
```
```
Returns: 0.21875
```
Two players, five pairs of bottles. It is quite unlikely that both players will win, somewhat more likely that only the second player wins, and even more likely that both of them lose.
```
16
```
```
18
```
```
Returns: 7.0000762939453125
```
The scenario from the unnamed TV show. Did the actual players do better or worse than the expected result? No spoilers!

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.