Problem: fightingthezombie (2017 quals)

**"Okay, Wizard, cast your spell!"**

But which of your many spells to cast? In the ever-popular role-playing game
_Dungeons & Dragons_, or _D&D_, you determine a spell's damage by rolling
polyhedral dice with 4, 6, 8, 10, 12, or 20 sides. Since there's a lot of
dice-rolling involved, players use shorthand to denote which dice should be
rolled. **X**d**Y** means "roll a **Y**-sided die **X** times, and sum the
rolls''. Sometimes, you must add or subtract a value **Z** after you finish
rolling, in which case the notation is **X**d**Y**+**Z** or **X**d**Y**-**Z**
respectively.

For example, if you roll 2d4+1, you'll end up with a result between 3 and 9
inclusive. If you roll 1d6-3, your result will be between -2 and 3 inclusive.

In _D&D_, wizards are powerful but flimsy spellcasters. As a wizard fighting a
zombie, your best strategy is to maximize the chance that you can kill the
zombie with a single spell before it has a chance to retaliate. What spell
should you cast?

### Input

Input begins with an integer **T**, the number of zombies you'll fight. For
each zombie, there are two lines. The first contains two integers, **H** and
**S**, the minimum amount of damage it takes to defeat the zombie, and the
number of spells you have prepared, respectively. The second line contains
**S** spell descriptions separated by single spaces. A spell description is
simply the amount of damage a spell does in the notation described above.

### Output

For each zombie, print a line containing the probability of defeating the
zombie if you select your spell optimally.

Absolute and relative errors of up to 1e-6 will be ignored.

### Constraints

1 ≤ **T** ≤ 1,000  
1 ≤ **H** ≤ 10,000  
2 ≤ **S** ≤ 10  

Additionally, the following constraints will hold for each spell:

1 ≤ **X** ≤ 20  
**Y** ∈ {4, 6, 8, 10, 12, 20}   
1 ≤ **Z** ≤ 10,000, if **Z** is specified.  
**X**, **Y**, and **Z** will be integers with no leading zeros.   

### Explanation of Sample

In the first case, you can guarantee a kill with the first spell, which must
always do at least 2 damage.

In the third case, your first spell is the best. If you roll a 4, you'll do
the requisite 8 damage. The second spell requires rolling a 4 on two dice
rather than just one, and the third spell requires rolling a 4 on all three
dice.



Sample input:
5
2 2
2d4 1d8
10 2
10d6-10 1d6+1
8 3
1d4+4 2d4 3d4-4
40 3
10d4 5d8 2d20
10 4
1d10 1d10+1 1d10+2 1d10+3


Sample output:
Case #1: 1.000000
Case #2: 0.998520
Case #3: 0.250000
Case #4: 0.002500
Case #5: 0.400000



Code: // Hacker Cup 2017
// Qualification Round
// Fighting The Zombie
// Wesley May

import java.util.*;

public class FightingTheZombie 
{
	static int H;

	public static void main(String args[])
	{
		double EPS = 0.000001;
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();

		for(int ca=1;ca <= T;ca++)
		{
			H = scan.nextInt();
			int S = scan.nextInt();
			Spell[] a = new Spell[S];

			for(int i=0;i < S;i++)
			{
				String str = scan.next();
				int X, Y, Z;

				int didx = str.indexOf("d");
				int plusidx = str.indexOf("+");
				int minusidx = str.indexOf("-");

				X = Integer.parseInt(str.substring(0, didx));

				if(plusidx >= 0)
				{
					Y = Integer.parseInt(str.substring(didx+1, plusidx));
					Z = Integer.parseInt(str.substring(plusidx));
				} 
				else if(minusidx >= 0)
				{
					Y = Integer.parseInt(str.substring(didx+1,minusidx));
					Z = Integer.parseInt(str.substring(minusidx));
				}
				else
				{
					Y = Integer.parseInt(str.substring(didx+1));
					Z = 0;
				}

				a[i] = new Spell(X, Y, Z);
			}

			Arrays.sort(a);

			System.out.printf("Case #%d: %.6f\n", ca, a[0].p);
		}
	}

	static class Spell implements Comparable<Spell>
	{
		int x, y, z;
		public double p;
		double[][] dp;

		public Spell(int ix, int iy, int iz)
		{
			x = ix;
			y = iy;
			z = iz;
			int newH = H - z;

			if(newH <= 0)
			{
				p = 1;
				return;
			}

			dp = new double[newH+1][x+1];
			for(int i=0;i < dp.length;i++)
				Arrays.fill(dp[i], -1);

			p = f(newH, x);
		}

		private double f(int h, int d)
		{
			if(h <= 0) return 1;
			if(d == 0) return 0;
			if(dp[h][d] >= 0) return dp[h][d];

			double ans = 0;
			for(int i=1;i <= y;i++)
			{
				ans += (1.0 / y) * f(h-i, d-1);
			}

			return dp[h][d] = ans;
		}

		public int compareTo(Spell that) {
			if(this.p > that.p) return -1;
			if(this.p < that.p) return 1;
			return 0;
		}
	}
}