J. Jumanji
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice, Bob,and Cindy are playing the exciting board game Jumanji. If you die in the game, you die for real!

Each of them starts with $$$a$$$, $$$b$$$, and $$$c$$$ points of HP (Health Points) respectively.

All gameplay takes place on a long path with $$$n+1$$$ squares, labeled $$$0$$$ to $$$n$$$. Each square has a damage value written on it—the damage value of square $$$i$$$ is $$$d_i$$$. You are guaranteed that $$$d_0 = d_n = 0$$$.

Gameplay goes as follows:

  • All three of them start on square $$$0$$$. The goal is to reach square $$$n$$$.
  • The three of them take turns rolling a pair of fair six-sided dice, with turn order: Alice, then Bob, then Cindy (then back to Alice).
  • The turn player moves a number of steps forward equal to the sum of the two die rolls (or up to square $$$n$$$ only, if the number of steps they would take would make them go past square $$$n$$$).
  • Then, the damage value of the square they stop on is subtracted from their HP. If their HP ever equals $$$0$$$ or below at any given time, they die (forever).
  • The game ends when all three have reached square $$$n$$$ alive.
Find the probability that all three of them survive Jumanji.
Input

The first line of input contains the four space separated integers $$$n$$$, $$$a$$$, $$$b$$$, $$$c$$$.

The second line contains the $$$n+1$$$ space-separated integers $$$d_0, d_1, d_2, \dots, d_n$$$.

Output

Output a single line containing a single real number denoting the probability that all three of them survive Jumanji.

Your answer will be considered correct if the absolute error between it and the judge's answer is at most $$$10^{-12}$$$. In other words, if $$$a$$$ is the correct answer and $$$a_0$$$ is your answer, then it is accepted if $$$$$$ |a - a_0| \leq 10^{-12}. $$$$$$ Remember to output your solution to sufficiently many decimal places.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 200 \\ 1 \leq a, b, c \leq 2024 \\ \text{$1 \leq d_i \leq 2024$ for $0 \lt i \lt n$} \\ d_0 = d_n = 0 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & n \leq 5 \\ \hline 2 & \mathbf{25} & n \leq 7 \\ \hline 3 & \mathbf{25} & d_i, a, b, c \leq 70 \\ \hline 4 & \mathbf{25} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Examples
Input
4 10 20 30
0 12 8 15 0
Output
0.94444444444444441977
Input
11 10 20 30
0 1 1 5 2 3 5 1 8 12 9 0
Output
0.75393091994762695407