Wallpaper Rolls
National Olympiad — Municipal round (2013 season)
Submission name: wallpaper.cpp
Problem summary
Cover a wall of height N metres and width M metres with vertical, unjoined, one-metre-wide strips. Rolls are one metre wide and K metres long. Find the fewest rolls when a full-height strip can be cut.
Source clarification. The PDF permits zero dimensions and K<N but defines no impossible-case output. Zero-area walls are handled naturally as 0 rolls. For a positive wall with K<N the program exits without inventing an output value; the worked solution applies to feasible positive-wall inputs. The official analysis uses the same floor-then-ceiling formula; all 11 released official tests have positive feasible dimensions.
Input
Three integers N, M, K.
Output
The minimum number of rolls for feasible positive-wall inputs; a zero-area wall needs zero rolls.
Constraints
0 ≤ N,M,K ≤ 10^18. For a positive-area wall, the described construction is feasible only if K ≥ N > 0.
Worked example
An independently prepared example for this explanation.
Input
10 5 25
Output
3
Solution analysis
- For positive wall height, each roll yields stripsPerRoll = floor(K/N) whole strips. Any shorter remainder is discarded.
- The wall needs M strips. Compute ceil(M/stripsPerRoll) using quotient plus a nonzero-remainder test; this avoids adding two values as large as 10^18.
- For height 10 and roll length 25, each roll gives two usable strips and wastes five metres. Five strips therefore need three rolls.
Why it works
Every roll supplies at most floor(K/N) strips, so fewer than the ceiling count cannot cover M strips. Cutting that many rolls into full-height pieces supplies at least M strips and covers the wall, attaining the bound.
Watch out. Use 64-bit integers. Multiplying dimensions is unnecessary and can overflow. Check zero area before dividing. A positive wall with K<N cannot be covered; the PDF specifies no output for this case.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long height, width, length;
cin >> height >> width >> length;
if (height == 0 || width == 0) {
cout << 0 << '\n';
return 0;
}
// The statement gives no output when a positive wall is impossible.
if (length < height) {
return 0;
}
// Count whole strips, then take the ceiling without a large addition.
long long stripsPerRoll = length / height;
cout << width / stripsPerRoll + (width % stripsPerRoll != 0) << '\n';
}