PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: tanminati
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Basic math
PROBLEM:
Find the minimum number of rooms needed to accommodate B boys and G girls in a hotel, while satisfying the following:
- Each room must have at least X boys.
- Each room must have at least Y boys.
- Each room must have at most N people.
If it’s impossible, print -1.
EXPLANATION:
Let’s try to find a couple of bounds on the answer.
There are B+G people in total, and each room can have at most N people.
So, we certainly need at least
rooms, where \left\lceil x \right\rceil denotes the ceiling of x, i.e. the smallest integer that’s not smaller than x.
Let R = \left\lceil \frac{B+G}{N} \right\rceil.
We need at least R rooms with a positive number of people.
As per the constraints, each of these rooms must contain at least X boys and Y girls each.
This is only possible when we have at least R\cdot X boys and R\cdot Y girls, i.e.
Now, if both these conditions are satisfied, it’s surely possible to use exactly R rooms.
For example, we can first put X boys and Y girls in each of the R rooms; and then distribute the remaining people however we like (while not exceeding N per room); because R\cdot N \ge B+G we’ll have enough space to fit everyone.
Thus, in this case the answer is R.
On the other hand, if one of these conditions fail, observe that no solution can exist.
For example, suppose R\cdot X \gt B.
Then, with R rooms we don’t have enough boys to place X in every room.
However, R was our lower bound on the answer: so going with a higher number of rooms means we’ll still be unable to satisfy the X-boys-per-room constraint.
Thus, with R = \left\lceil \frac{B+G}{N} \right\rceil,
- If R\cdot X \le B and R\cdot Y \le G, the answer is R.
- Otherwise, the answer is -1.
To compute \text{ceil}\left(\frac{X}{Y}\right) where both X and Y are positive, you can use the identity \text{ceil}\left(\frac{X}{Y}\right) = \text{floor}\left(\frac{X+Y-1}{Y}\right).
This is convenient because floor division is what is naturally implemented in most programming languages when you divide integers (like / in C++ or // in Python).
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
b, g, x, y, n = map(int, input().split())
tot = b+g
req = (tot + n - 1) // n # ceil(tot / n)
if req*x <= b and req*y <= g: print(req)
else: print(-1)