DMPG '17 B3 - Heroes - Olympiads Online Judge

DMPG '17 B3 - Heroes

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 64M

Author:

Kirito

Problem type

Roger is addicted to the game Fire Emblem Heroes! His main hero is Hector, who has $h_H$ ~h_H~ health and deals $d_H$ ~d_H~ damage per turn. Hector is up against a foe who deals $d_F$ ~d_F~ damage per turn, and has $h_F$ ~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$ ~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.

Constraints

Subtask 1 [60%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

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

Subtask 2 [40%]

$1 \le N \le 10^6$ ~1 \le N \le 10^6~

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

Input Specification

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

Output Specification

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

Sample Input

Sample Output

Win 1
Lose 1
Win 1
Win 4

Comments

2

geese commented on Jan. 1, 2020, 12:53 a.m.

https://www.youtube.com/watch?v=02kKKQ3JWPY

5
4fecta commented on July 5, 2019, 2:57 a.m. ← edit 4 →
Test cases are too weak. Most participants passed with brute force, while the time complexity for brute force is around $\mathcal{O}(N \times \min(Hh/Df, Hf/Dh))$ . This has a worst case of $\mathcal{O}(10^6 \times 10^9)$ ~\mathcal{O}(10^6 \times 10^9)~, which is far too inefficient.

Edit:

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