Packing Four Cubes
National Olympiad — Municipal round (2022 season)
Submission name: package.cpp
Problem summary
Four cubic devices have side lengths A ≤ B ≤ C ≤ D. Pack them into as few cubic boxes of side E as possible. Several devices may share a box, and empty space may be filled with packing granules.
Input
A B C D E, one integer per line.
Output
The minimum number of boxes.
Constraints
1 ≤ A ≤ B ≤ C ≤ D ≤ E ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
1 2 3 4 7
Output
1
Solution analysis
- Two cubes can share a box when their side lengths sum to at most E. Up to four cubes whose every pair satisfies this condition can share one box: place them at corner patterns 000,110,101,011, keeping their faces parallel to the box faces. Every pair is separated along some coordinate.
- Because A ≤ B ≤ C ≤ D, all four fit together exactly when C+D ≤ E. Otherwise, two boxes suffice if B+C ≤ E: put A,B,C in one box and D in the other. If that fails, three boxes suffice when A+B ≤ E. Otherwise all four need separate boxes.
- For side lengths 1,2,3,4 and E=7, the largest pair sums to 7, so the four-corner placement fits everything in one box. For four devices of side 2 and E=2, even the smallest pair does not fit, so four boxes are necessary.
Why it works
If C+D ≤ E, every pair fits and the corner construction packs all four. Otherwise C and D force at least two boxes. If B+C ≤ E, A,B,C share a box, attaining two. If B+C > E, B,C,D are pairwise incompatible and force at least three boxes. If A+B ≤ E, packing that pair and leaving C,D separate attains three. Otherwise every pair is incompatible, so exactly four boxes are necessary.
Watch out. Volumes alone cannot decide whether cubes fit. The input side lengths are sorted. Equality with the box side is allowed; use ≤ rather than <.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int a, b, c, d, boxSide;
cin >> a >> b >> c >> d >> boxSide;
// The largest compatible group determines how many boxes remain necessary.
if (c + d <= boxSide) {
cout << 1 << '\n';
} else if (b + c <= boxSide) {
cout << 2 << '\n';
} else if (a + b <= boxSide) {
cout << 3 << '\n';
} else {
cout << 4 << '\n';
}
}