Explosion Exploit
Time limit3sMemory limit512 MB
Given up to 10 minions with health at most 6 and d up to 100, find the chance that uniformly random sequential damage kills every opposing minion.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Combinatorics, Probability
- Solved
- No attempts yet
Problem
In a two player card game, you have n minions on the board and the opponent has m minions. Each minion has a health between 1 and 6.
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 ≤ n, m ≤ 5, 1 ≤ d ≤ 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.