PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You want to buy a total of N kg of weights.
You can buy 1 kg for 20 rupees, or 2 kg for 30 rupees.
Find the minimum total cost of buying exactly N kg.
EXPLANATION:
We will never buy more than one 1 kg weight, because buying two of them gives us 2 kg for a total of 20+20 = 40 rupees when it would’ve been cheaper to just directly buy 2 kg for 30 rupees.
So,
- If N is even, we will buy the 2 kg weight \frac{N}{2} times, for a total cost of \frac{N}{2} \cdot 30.
- If N is odd, we will buy the 2 kg weight \frac{N-1}{2} times and the 1 kg weight one time, for a total cost of \frac{N-1}{2} \cdot 30 + 20.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
print(30*(n//2) + 20*(n%2))