Problem C
Hi-Ho! Kumquat-O
Hi-Ho! Kumquat-O is a popular children’s board game where four players race to harvest all ten kumquats from their kumquat tree. The players take turns in order; on each turn, a player spins a spinner and carries out the instructions appropriate to the outcome of the spinner. You may assume that the spinner lands on one of the possible outcomes uniformly at random. The possible spinner outcomes are as follows:
-
$1$: the player removes one kumquat from their tree.
-
$2$: the player removes two kumquats from their tree.
-
$3$: the player removes three kumquats from their tree.
-
$4$: the player removes four kumquats from their tree.
-
Half: the player removes half the remaining kumquats from their tree, rounded down (unless there is only $1$ kumquat remaining, in which case they remove it). For example, if there are four kumquats remaining, the player removes two; if three remaining, they remove one.
-
Kumquat-O: the player removes one kumquat, then spins again.
The game ends immediately when the number of kumquats on any player’s tree becomes zero. If a player spins $2$, $3$, or $4$ and there are fewer kumquats remaining on their tree than the number they landed on, they simply remove all the remaining kumquats (and therefore win).
Ivan has been co-opted by some local children into playing this tedious game, and is wondering how much longer he will have to play.
Input
The first line of input contains four space-separated integers $k_1\; k_2\; k_3\; k_4$ ($1 \leq k_i \leq 10$) where each $k_i$ indicates the number of kumquats remaining on player $i$’s tree. The second line of input contains a single integer $t$ ($1 \leq t \leq 4$) indicating which player’s turn it is.
Output
Output a single floating-point number giving the expected number of turns until the game ends, including both the turn of the player whose turn it is as well as the final turn on which someone reduces their kumquats to zero. Your answer will be considered correct if has an absolute or relative error of at most $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 5 7 3 1 |
1.0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 1 1 1 |
1.5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 8 4 7 3 |
4.29113579966 |
