XYZ343 - Editorial

editorial
,
1

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 \geq \frac{X\cdot Y - Z}{Y}

K must be an integer, so choose

K = \left\lceil \frac{X\cdot Y - Z}{Y} \right\rceil

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)