PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
901
PREREQUISITES:
None
PROBLEM:
Chef’s phone battery is currently at N percent, and he wants it to reach exactly 50 percent.
Each minute, the battery can either increase by 2 percent, or decrease by 3 percent.
What’s the minimum time needed for the battery to reach 50 percent?
EXPLANATION:
There is an obvious greedy simulation approach here:
- If the battery is \gt 50, reduce it by 3.
- If the battery is \lt 50, increase it by 2.
- If the battery equals 50, stop.
This greedy is correct, and so directly simulating it is enough to get AC.
This simulation can be done using a while
loop and if
conditions.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
ans = 0
while n != 50:
if n > 50: n -= 3
else: n += 2
ans += 1
print(ans)