Picnic Drinks
National Olympiad — Municipal round (2012 season)
Submission name: piknik.cpp
Problem summary
Each of k pupils drinks two 200 ml cups. A bottle holds l litres and ml additional millilitres. Find the fewest bottles that supply everybody.
Source clarification. The PDF prints l ≥ 1 but its first sample uses l = 0. The solution supports that sample; a zero-capacity bottle has no defined answer in the statement.
Input
Three integers k, l, ml.
Output
The number of bottles to buy.
Constraints
1 ≤ k ≤ 26; printed bounds give 1 ≤ l ≤ 20 and 0 ≤ ml < 1000, but an official sample uses l = 0. Bottle capacity must be positive.
Worked example
An independently prepared example for this explanation.
Input
26 0 500
Output
21
Solution analysis
- Convert everything to millilitres: total demand is 400*k and bottle capacity is 1000*l+ml.
- Divide demand by capacity, adding one bottle when the remainder is nonzero. This is integer ceiling division.
- For 26 pupils, demand is 10400 ml. Twenty 500 ml bottles give only 10000 ml, so 21 are necessary.
Why it works
The ceiling is the smallest integer bottle count whose product with capacity reaches the demand. Every smaller count supplies too little, and the computed count supplies enough.
Watch out. Do not round down. Treat litres and millilitres as parts of one capacity.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int pupils, litres, millilitres;
cin >> pupils >> litres >> millilitres;
int capacity = 1000 * litres + millilitres;
int demand = 400 * pupils;
// Add a bottle only when the exact division leaves a remainder.
cout << demand / capacity + (demand % capacity != 0) << '\n';
}