For each attack, we need to compute the probability that it rolls at least ~H~ damage. We can compute this using dynamic programming.

Let ~f(D, K)~ be the probability of dealing at least ~K~ damage with ~D~ dice. For a given input ~X\ Y\ Z~, we want to compute ~f(X, H-Z)~. We can use the following recursive definition:

• ~f(D, K) = 1~ for ~K \le 0~ (We can always do at least ~0~ damage)
• ~f(0, K) = 0~ for ~K > 0~ (We can't do a positive amount of damage with ~0~ dice)
• ~f(D, K) = \frac 1 Y \sum_{d=1}^Y f(D-1, K-d)~

This last formula combines the outcomes of all possible die rolls for a single die, and weights them evenly by ~\frac 1 Y~.

In this way, we can compute the probability of success for each attack in ~\mathcal O(XY(H-Z))~ time.

Since the most damage we can do is ~XY~, we can trivially reject any case where ~H-Z > XY~. That means we can also consider the time complexity to be ~\mathcal O(XYXY) = \mathcal O(X^2 Y^2)~.