PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author & Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given the attack power X of a monster, and the health H of its opponent.
Each turn, the monster does X damage to its opponent.
However, for the first 5 turns, it does \frac{X}{2} damage instead.
How many turns will it take to defeat its opponent?
EXPLANATION:
The constraints are quite low, so even direct simulation is enough to get AC.
That is, go turn by turn: if the turn number is \leq 5, subtract \frac{X}{2} from H; otherwise subtract X. This way, all you need to do is see when you reach H \leq 0.
The complexity of simulation is \mathcal{O}(H).
It’s also possible to solve this problem mathematically.
There are two separate ‘phases’ to the fight: the first five turns, and everything else.
Let Y = \frac{X}{2}. Then,
- If 5Y \geq H, the fight will finish within the first five turns.
So, the answer is \left\lceil \frac{H}{Y} \right\rceil - If 5Y \lt H, the fight won’t finish within 5 turns.
In this case, the answer is 5 + \left\lceil \frac{H - 5Y}{X}\right\rceil, because we remove exactly 5Y health in the first 5 turns, and then X health every turn after that.
Here, \left\lceil \ \right\rceil denotes the ceiling function.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
Author's code (Python, simulation)
for _ in range(int(input())):
x, h = map(int, input().split())
dmg, moves = 0, 0
while dmg < h:
if moves < 5: dmg += x//2
else: dmg += x
moves += 1
print(moves)
Author's code (Python, math)
for _ in range(int(input())):
x, h = map(int, input().split())
half = x//2
if 5*half >= h: print((h + half - 1) // half)
else: print(5 + ((h - 5*half + x - 1) // x))