PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: apoorv_me, tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Chef has X income sources, each giving him Y rupees.
He can hold at most Z rupees in his bank account.
What’s the minimum number of sources that have to be reduced so that Chef doesn’t exceed his account’s limit?
EXPLANATION:
If Chef reduces the number of sources by K, he will have (X-K) income sources, each giving him Y rupees.
This is a total income of (X-K)\cdot Y rupees.
Since his bank account can hold Z rupees, he wants (X-K)\cdot Y \leq Z to hold.
Simply try each K = 0, 1, 2, \ldots, X to find the smallest one for which this inequality holds.
Alternately, the problem can be solved with a bit of math.
If X\cdot Y \leq Z initially, the answer is 0.
Otherwise, you want the smallest integer K such that (X-K)\cdot Y \leq Z.
Rearranging this, we see that K\cdot Y \geq X\cdot Y - Z, meaning
K must be an integer, so choose
Here, \left\lceil \ \ \right\rceil denotes the ceiling function.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x, y, z = map(int, input().split())
if x*y <= z: print(0)
else: print((x*y - z + y - 1) // y)