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 \leq N \leq 1 000$

$1 \le h_H, d_H, h_F, d_F \le 100$ $1 \leq h_{H}, d_{H}, h_{F}, d_{F} \leq 100$

Subtask 2 [40%]

$1 \le N \le 10^6$ $1 \leq N \leq 10^{6}$

$1 \le h_H, d_H, h_F, d_F \le 10^9$ $1 \leq h_{H}, d_{H}, h_{F}, d_{F} \leq 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

Copy

Sample Output

Copy

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))$ $O (N \times min (H h / D f, H f / D h))$ . This has a worst case of $\mathcal{O}(10^6 \times 10^9)$ $O (10^{6} \times 10^{9})$ , which is far too inefficient.

Edit:

Test case that cracks most submissions:

Copy
10 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1