SLOWSTART - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author & Editorialist: iceknight1093






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?


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.


\mathcal{O}(1) per testcase.


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
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))
1 Like