All Painted-Face Counts in a Cuboid
National Olympiad — Municipal round (2018 season)
Submission name: kub.cpp
Problem summary
All exterior faces of an A-by-B-by-C block of unit cubes are painted. Count unit cubes with exactly0,1,…,6 painted faces, including thin dimensions.
Input
A B C.
Output
Seven counts in increasing painted-face order.
Constraints
1 ≤ A,B,C ≤1000.
Worked example
Input and output for the worked example discussed below.
Input
2 3 4
Output
0 4 12 8 0 0 0
Solution analysis
- For an axis of length L≥2, there are L−2 interior positions contributing0 painted faces and two endpoints contributing1. For L=1 there is one position contributing2 opposite painted faces.
- Make these three small distributions independently for x,y,z. For every contribution triple i,j,k, multiply the numbers of positions and add that product to answer[i+j+k]. Only27 combinations are needed.
- For dimensions2,3,4, the distributions are(0,2,0),(1,2,0),(2,2,0). Their products give0 cubes with zero faces,4 with one,12 with two,8 with three, and none with four or more.
Why it works
Painted faces perpendicular to different axes contribute independently. Choosing one coordinate from each axis uniquely identifies a unit cube, and its painted total is the sum of the three axis contributions. The product-and-sum enumeration therefore counts every cube once in the correct bin.
Watch out. A dimension of1 contributes both opposite faces, not one. Enumerating up to10^9 cubes is unnecessary; use64-bit products for clarity.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
long long distribution[3][3]={};
for(int axis=0;axis<3;axis++){
int length;
cin>>length;
if(length==1){
distribution[axis][2]=1;
}
else{
distribution[axis][0]=length-2;
distribution[axis][1]=2;
}
}
long long answer[7]={};
for(int x=0;x<=2;x++){
for(int y=0;y<=2;y++){
for(int z=0;z<=2;z++){
// Coordinate choices are independent across the three axes.
answer[x+y+z]+=distribution[0][x]*distribution[1][y]*distribution[2][z];
}
}
}
for(int faces=0;faces<=6;faces++){
if(faces>0){
cout<<' ';
}
cout<<answer[faces];
}
cout<<'\n';
}