SLOWSTART - Editorial

editorial
,
1

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