CannonballPyramids
TCO2020 EastAsia Qualification · 2020-09-24 · by misof
Problem Statement
A square cannonball pyramid of size S is an arrangement of cannonballs into S layers. The bottom layer is a square consisting of S*S cannonballs. The next layer is a square of (S-1)*(S-1) cannonballs, placed into the gaps between the cannonballs forming the bottom layer. And so on: each of the following layers is also a square, and in each layer the side of that square decreases by 1. The top layer consists of a single cannonball.
You have B cannonballs.
Use all of them to build at most six perfect square cannonball pyramids.
Return a
If there are multiple solutions, all will be accepted.
If there is no solution, return an empty
Notes
- You do not have to minimize the number of pyramids built, any solution with at most six of them is valid.
- You must use all cannonballs you have.
Constraints
- B will be between 1 and 10^9, inclusive.
280
Returns: {7, 7 }
A pyramid of size 7 has 7*7 + 6*6 + ... + 2*2 + 1*1 = 140 cannonballs. You can build two such pyramids.
6
Returns: {1, 1, 1, 1, 1, 1 }
You can build six pyramids of size 1 each. It's a valid solution, even though it does not use the smallest number of pyramids - that would be a pyramid of size 2 and a pyramid of size 1. (Also, it's the laziest solution, you do not have to stack any cannonballs at all, you just let them all lie on the floor.)
1253620
Returns: {2, 9, 155 }
Order of pyramids in the output does not matter. E.g., {9, 155, 2 } is also a valid answer.
4608
Returns: {2, 10, 18, 18 }
1
Returns: {1 }
Submissions are judged against all 161 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CannonballPyramids with a public method vector<int> build(int B) · 161 test cases · 2 s / 256 MB per case