WEPCH - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Find the minimum needed to defeat a boss with H health, with one of the following weapons:

  • A gun that does X damage per hit; and
  • A laser that does Y_1 damage for K hits, then Y_2.

EXPLANATION:

Let’s calculate the number of hits needed for the gun and the laser separately, the answer is then their minimum.

For the gun, the situation is simple: we do X damage per hit, so \left\lceil \frac{H}{X} \right\rceil hits are needed to do \geq H damage.
\left\lceil \ \ \right\rceil denotes the ceiling function.

For the laser, there are a couple of possibilities:

  • First, if K\cdot Y_1 \geq H, the laser will defeat the boss before ever dropping in output.
    In this case, it would need \left\lceil \frac{H}{Y_1} \right\rceil hits.
  • Otherwise, K\cdot Y_1 \lt H, so the laser’s output drops.
    Then, the first K hits do a total of K\cdot Y_1 damage, and then we’re stuck with Y_2 for the remainder.
    This needs K + \left\lceil \frac{H - K\cdot Y_1}{Y_2} \right\rceil hits in total.

Once the values for the gun and the laser are computed, print their minimum.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    h, x, y1, y2, k = map(int, input().split())
    gun = (h + x - 1) // x
    laser = 0
    if y1*k >= h: laser = (h + y1 - 1) // y1
    else: laser = k + (h - k*y1 + y2 - 1) // y2
    print(min(gun, laser))
1 Like