Fighting the Zombie

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 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. XdY 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 XdY+Z or XdY-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 Specification

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 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 10^{-6} will be ignored.


1 \le T \le 1\,000

1 \le H \le 10\,000

2 \le S \le 10

Additionally, the following constraints will hold for each spell:

1 \le X \le 20

Y \in \{4, 6, 8, 10, 12, 20 \}

1 \le Z \le 10\,000 if Z is specified.

X, Y, and Z will be integers with no leading zeros.

Sample Input

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 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.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.


There are no comments at the moment.