Problem C
Inkay Game
$456$ Pokémon in crippling debt are recruited to play the dangerous “Inkay Game.” In one round of the game, there are $N$ Pokémon contestants numbered from $1$ to $N$ trying to cross a bridge of glass platforms of $L$ pairs of side-by-side glass steps. In each pair, one step is stable, and one step will permanently break upon being stepped on, eliminating the contestant that stepped on it. Whenever a contestant steps on one step in a pair, all contestants will thus know which step of the pair is safe, regardless of whether or not it breaks.
The contestants take turns stepping onto the first untested pair of steps. Upon testing a pair, there is a $50\% $ chance that the contestant chooses wrong and is eliminated, but either way, that pair will stay “discovered” and all contestants will be able to cross it going forward. Once all pairs have been tested, then remaining contestants can cross the bridge.
Who tests the next pair of steps is determined as follows:
-
If only one contestant remains, they test the next pair.
-
Otherwise, the group always starts out pressuring the contestant with the lowest number.
-
Each contestant refuses to step with probability $p$, in which case the group pressures the remaining contestant with the next lowest number.
-
If all contestants refuse to step, then the group pushes the remaining contestant with the lowest number off the bridge, eliminating them.
After a step is tested or a contestant is pushed off the bridge, the pressure goes back to the remaining contestant with the lowest number.
What is the probability that at least one contestant makes it across all steps?
Input
The input has with one line containing three space-separated numbers, $N$, $L$, and $p$, where $N$ and $L$ are integers and $p$ is a real number. These denote the number of contestants $1 \leq N \leq 3000$, the number of pairs of steps in the bridge $1 \leq L \leq 3000$, and the probability that any contestant will refuse to step when pressed by others, $0 \leq p \leq 1$.
Output
Output one line containing the probability that at least one contestant makes it across all steps. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-5}$.
Sample Explanation
In the first sample case, no contestant will refuse to step. The chance that one contestant makes it across is the probability of fewer than two failures within $5$ attempts, or $\frac{6}{32}$.
In the second sample case, there is a $\frac14$ chance both refuse, and the first contestant is pushed off. The second contestant then has a $\frac12$ chance of guessing the next step. In the case that least one agrees to take the first step, then whatever happens, the remaining contestant will know which step in the sole pair is safe and make it across.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 5 0 |
0.1875 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 0.5 |
0.875 |
