Problem K
First Orchard
First Orchard is a cooperative game for children 2 years and up. In this simple game, the players pick colored fruits from trees in an orchard and place them into a basket. To make the game more interesting, a raven tries to reach the orchard to steal the fruits. If the players are successful in moving all fruits into the basket before the raven can get to the orchard, they’ll win. If the raven gets there first, the players lose!
Your task is to determine the probability with which the players will win!
The game is played as follows. There are $4$ trees in the orchard, each bearing a different type of fruit: red apples, green apples, blue plums, and yellow pears. The raven tries to reach the orchard through a pathway containing one or more steps.
At each turn, the players roll a six-sided die. Four of the faces show a color (red, green, yellow, blue), the fifth face shows a fruit basket, and the sixth face shows a raven. All six faces can appear with equal probability.
-
Red, Green, Yellow, Blue. In these cases, a fruit with the corresponding color is placed into the basket, provided the tree corresponding to this color still has any fruits left to pick. Otherwise, the players move on to the next turn.
-
Fruit Basket. If the players roll the ’basket’ face, they will pick a fruit from the tree that has the largest number of fruits left. If there are multiple such trees with the same number of fruits, any of the trees can be chosen.
-
Raven. If the ’raven’ face appears on the die, then the raven moves one step closer towards the orchard.
The game is over if either the players have picked all fruits, or if the raven reaches the orchard, whichever happens first. If the raven reaches the orchard before the players have placed all fruits into the basket, the players lose.
Input
The input consists of a single test case with a single line of input. The input contains five integer numbers: $R$, $G$, $B$, $Y$ and $S$. The values of $R, G, B$ and $Y$ are the number of red, green, blue, and yellow fruits initially on each tree, respectively, and $S$ denotes the number of steps on the raven’s pathway. Since the game is intended for young children, there will be at most $4$ fruits of each color: $0 \le R, G, B, Y \le 4$. There will be at least one fruit overall: $0 < R + G + B + Y$. The raven will require at least $1$ and at most $8$ steps: $1 \le S \le 8$. The number of steps is equal to the number of times the raven must appear on the die for the players to lose.
Output
Output the probability that the players will win as a floating point number. The absolute error of your result should be less than $10^{-5}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 0 0 3 |
0.920138888889 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 4 4 5 |
0.631357306601 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 4 4 4 4 |
0.459393713591 |
