DMPG '17 B3 - Heroes

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.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

Roger is addicted to the game Fire Emblem Heroes! His main hero is Hector, who has h_H health and deals d_H damage per turn. Hector is up against a foe who deals d_F damage per turn, and has h_F health. However, Hector's special, Buckler, activates every 4th turn and negates all damage done against him in that turn, as well as continues to deal the regular amount of damage.

Given N of these enemies, can you find out who will come out victorious if Hector attacks first, and how many turns it will take?

Note: assume the turn counter, as well as Hector's health, reset with each foe.


Subtask 1 [60%]

1 \le N \le 1\,000

1 \le h_H, d_H, h_F, d_F \le 100

Subtask 2 [40%]

1 \le N \le 10^6

1 \le h_H, d_H, h_F, d_F \le 10^9

Input Specification

Line 1: Three space separated integers, N, h_H, and d_H.
Lines 2 \ldots N + 1: Two space separated integer, the h_F and d_F for each foe.

Output Specification

N lines, of the format Win x if Hector wins in x turns, or Lose x, if Hector loses in x turns.

Sample Input

4 12 5
4 2
999 999
5 12
20 3

Sample Output

Win 1
Lose 1
Win 1
Win 4


  • 3
    geese  commented on Dec. 31, 2019, 7:53 p.m.

  • 5
    4fecta  commented on July 4, 2019, 10:57 p.m. edit 3

    Test cases are too weak. Most participants passed with brute force, while the time complexity for brute force is around O(N x min(Hh/Df, Hf/Dh)). This has a worst case of O(10^6 x 10^9), which is far too inefficient.


    Test case that cracks most submissions:

    10 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1