PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Find the minimum number of months needed for Chef to buy a GPU, if:
- The GPU’s initial price is X, while you start with 0.
- The GPU’s price increases by Y every month, while you earn Z.
EXPLANATION:
If Z \le Y, then Chef’s earning isn’t enough to offset the price increase.
In this case there’s no way for Chef to be able to buy the GPU, so we print -1.
On the other hand, if Z \gt Y then Chef earns more each month, so he will eventually be able to afford the GPU.
There are now two ways to solve the problem.
The first method is to simply simulate the process: for each month 1, 2, 3, 4, \ldots in order, perform the appropriate changes to both the GPU’s price and Chef’s total coins, and then check if Chef is able to buy the GPU.
Because the constraints are small (X, Y, Z \le 100), this brute force is fast enough - it will take at most 100 days for Chef to have enough coins.
The second method is to use math.
Initially, the difference between the GPU price and Chef’s coins equals X-0 = X.
Every month, the GPU price increases by Y and Chef’s coins increase by Z, so the difference between them decreases by (Z - Y).
Chef can buy the GPU only when the difference becomes \le 0.
This will take
months, rounded up because months must be an integer.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y, z = map(int, input().split())
if y >= z: print(-1)
else: print((x + z - y - 1) // (z - y))