← All solutions

This problem is pretty much a standard knapsack problem. We can precompute a matrix back[k][N], indicating which pyramid to use if we have N cubes and are trying to produce a solution using k pyramids (or an indication that no such solution exists). This may seem like a huge matrix since N can be 10⁶, but one can easily check that, when there is a solution for N ≤ 10⁶, the smallest number of pyramids is at most 6, and the number of different pyramids is small. Then for every query N we find the smallest k such that back[k][N] is possible.

People who are more clever than me may also realize that the problem is also solvable brute force.