XJUMP - Editorial

PROBLEM LINK:

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

Author: Tejas Pandey
Testers: Nishank Suresh, Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

686

PREREQUISITES:

None

PROBLEM:

Chef can climb either Y stairs or 1 stair in a single move. What’s the minimum number of moves to reach stair X?

EXPLANATION:

If possible, it’s better to use one move to climb Y stairs rather than 1, since Y \geq 1.

That gives an easy greedy strategy.

  • Let C denote the current stair Chef is on.
  • If C+Y \leq X, use one move to climb Y stairs.
  • Otherwise, climb one stair.

Directly implementing this using a loop is enough to get AC.

Thinking a little more should also give you a simple formula for the answer:

\left\lfloor \frac{X}{Y} \right\rfloor + (X\bmod Y)

where (X\bmod Y) is the remainder when X is divided by Y, represented by X % Y in most languages.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    x, y = map(int, input().split())
    print(x//y + x%y)