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)