Problem D
Explosion Exploit
You are contemplating your next move. You want to play an “Explosion” spell which deals $d$ units of damage randomly distributed across all minions. The damage is dealt one unit at a time to some remaining minion on the board. Each living minion (including your own) has the same chance of receiving each unit of damage. When a minion receives a unit of damage, its health is decreased by one. As soon as the health of a minion reaches zero, it is immediately removed from the board, before the next damage is dealt. If there are no minions left on the board, any excess damage caused by the spell is ignored.
Given the current health of all minions, what is the probability that the Explosion will remove all of the opponent’s minions? Note that it does not matter if all your own minions die in the process as well, and the damage continues to be dealt even if all your own minions are gone.
Input
The first line of input contains the three integers $n$, $m$, and $d$ ($1 \le n, m \le 5$, $1 \le d \le 100$). Then follows a line containing $n$ integers, the current health of all your minions. Finally, the third line contains $m$ integers, the current health of all the opponent’s minions. All healths are between $1$ and $6$ (inclusive).
Output
Output the probability that the Explosion removes all the opponent’s minions, accurate up to an absolute error of $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 2 2 2 1 1 |
0.3333333333 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 3 12 3 2 4 2 3 |
0.1377380946 |
