Repeated Largest-Cube Decomposition
National Olympiad — National round (2015 season)
Submission name: cubes.cpp
Problem summary
Repeatedly form the largest possible cube from remaining unit cubes, subtract its volume, and continue until none remain. Count the constructions.
Input
One integer n.
Output
The number of cubes formed by the specified greedy process.
Constraints
0 < n < 8×10^18.
Worked example
Input and output for the worked example discussed below.
Input
134
Output
3
Solution analysis
- Find the largest integer side s satisfying s³≤remaining. Use integer binary search because floating cube roots can round incorrectly near huge perfect cubes.
- Test s≤remaining/s/s rather than first multiplying a trial cube. Once the largest feasible side is found, its volume is known to fit within the remaining signed 64-bit value.
- For 134, take 125, then 8, then 1, giving 3 cubes. This simulates the required largest-first process; it does not optimize the number of arbitrary cube summands.
Why it works
Feasibility is monotone in side length, so binary search returns the exact largest feasible side. Subtracting its volume performs one specified step. The side is at least one while the remainder is positive, so repeated steps terminate and their count is the answer.
Watch out. Avoid overflowing a trial s³ and avoid unchecked floating cube roots. Use long long for counts and volumes.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
long long remaining;
cin>>remaining;
int answer=0;
while(remaining>0){
long long left=1;
long long right=2000000;
long long side=1;
while(left<=right){
long long middle=(left+right)/2;
// Test cube feasibility without overflowing a trial multiplication.
if(middle<=remaining/middle/middle){
side=middle;
left=middle+1;
}
else{
right=middle-1;
}
}
remaining-=side*side*side;
answer++;
}
cout<<answer<<'\n';
}