PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef wants to buy exactly N flowers.
He can buy 2 flowers with 4 coins, or 3 flowers with 5 coins.
How many coins does he need, at minimum?
EXPLANATION:
Observe that it’s never optimal to purchase the pack of two flowers three (or more) times.
This is because, buying it three times gives 6 flowers for a cost of 12 coins; whereas we could instead obtain 6 flowers using 10 coins by buying the 3-pack twice.
This means, in an optimal solution, Chef will buy the 2-pack of flowers at most two times.
Now we can simply try to buy the 2-pack either 0,1, or 2 times, and see if the 3-pack will cover the remaining flowers (which is possible if and only if the remaining flower count is divisible by 3).
Try all three options, and take the best one.
In fact, it can be observed that only one option will work at all, i.e. there’s a unique choice of 0 \leq x \leq 2 such that N - 2x is divisible by 3. So, rather than try all options and take the minimum, we can just find this unique valid option and compute its cost.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
ans = 0
while n%3 != 0:
ans += 4
n -= 2
ans += 5*(n//3)
print(ans)