Facebook Hacker Cup 2017 Qualifying Round
"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 , , , , , or sides. Since there's a lot of dice-rolling involved, players use shorthand to denote which dice should be rolled. XdY
means "roll a -sided die times, and sum the rolls". Sometimes, you must add or subtract a value after you finish rolling, in which case the notation is XdY+Z
or XdY-Z
respectively.
For example, if you roll 2d4+1
, you'll end up with a result between and inclusive. If you roll 1d6-3
, your result will be between and 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 Specification
Input begins with an integer , the number of zombies you'll fight. For each zombie, there are two lines. The first contains two integers, and , the minimum amount of damage it takes to defeat the zombie, and the number of spells you have prepared, respectively. The second line contains spell descriptions separated by single spaces. A spell description is simply the amount of damage a spell does in the notation described above.
Output Specification
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 will be ignored.
Constraints
Additionally, the following constraints will hold for each spell:
if is specified.
, , and will be integers with no leading zeros.
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
Explanation of Sample
In the first case, you can guarantee a kill with the first spell, which must always do at least damage.
In the third case, your first spell is the best. If you roll a , you'll do the requisite damage. The second spell requires rolling a on two dice rather than just one, and the third spell requires rolling a on all three dice.
Comments