Paint for the Classroom
National Olympiad — Municipal round (2011 season)
Submission name: repair.cpp
Problem summary
A rectangular classroom has length L, width W, and height H meters. Paint all four walls, ignoring doors and windows; do not paint the ceiling. A can covers 16 square meters. Find the minimum whole number of cans.
Input
Three integers L, W, H.
Output
The minimum number of paint cans.
Constraints
1 ≤ L, W, H ≤ 1,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
8 8 2
Output
4
Solution analysis
- There are two walls of area LH and two of area WH. The total painted area is 2(L + W)H.
- The required can count is the ceiling of area/16. With integer arithmetic, compute (area + 15)/16 to round up any positive remainder.
- For L = 8, W = 8, H = 2, the wall area is 64 square meters. Four cans cover it exactly. For 1, 1, 3, the area is 12 and one can suffices.
Why it works
The area expression sums each of the four walls exactly once and excludes the ceiling. Any c cans cover at most 16c square meters, so c must be at least the ceiling of area/16. That many cans do cover the area, proving minimality.
Watch out. Use 64-bit arithmetic before adding or multiplying. Round up, but do not add a can when the area is exactly divisible by 16.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long length, width, height;
cin >> length >> width >> height;
// Two walls of each length; the ceiling is excluded.
long long area = 2 * (length + width) * height;
cout << (area + 15) / 16 << '\n';
}