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
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 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.
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.
Additionally, the following constraints will hold for each spell:
if is specified.
, , and will be integers with no leading zeros.
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
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.
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.