Problem Statement
Time limit: 3 seconds.
My little brother loves cotton candy. Last Christmas I decided to give him several rectangular boxes, each full of cotton candy. Of course, presents need to be wrapped properly.
Whenever I wrap a box, the amount of wrapping paper consumed is always exactly equal to the surface area of that box. (The shape of the available wrapping paper does not matter, I will use scissors and tape as needed.)
In the beginning I had paperArea square centimeters of wrapping paper and a sufficient supply of boxes with all possible integer side lengths (in centimeters).
When preparing the gifts for my little brother, I repeatedly selected the largest box I could still wrap (as explained below), filled it with cotton candy, and wrapped it. The process terminated when I reached the situation in which the remaining amount of wrapping paper wasn't sufficient to wrap any more gifts.
When selecting the next box to fill and wrap, I used the following rules. Let (A, B, C)-box be a box with dimensions A, B, C such that A <= B <= C. In each iteration of the above process I selected the triple (A, B, C) using the following rules:
- Among all boxes I can still wrap, pick the one for which A*B*C is maximized.
- If there are multiple such boxes, pick the one with the smallest possible A.
- If there are still multiple such boxes, pick the one with the smallest possible B.
You are given the number paperArea: the total area of the wrapping paper I had. Determine what boxes I wrapped and return the total volume of cotton candy I gave to my little brother.
Definition
- Class:
- Presents2023
- Method:
- pack
- Parameters:
- long
- Returns:
- long
- Method signature:
- long pack(long paperArea)
- (be sure your method is public)
Notes
- For the constraints given below the correct return value is guaranteed to fit into a signed 64-bit integer.
- Note that we are not trying to maximize the total volume of all the boxes. Instead, in each step separately we are maximizing the volume of the next box to be wrapped.
Constraints
- paperArea will be between 6 and 10^13, inclusive.
Examples
605
Returns: 1000
The biggest box I can wrap using 605 square centimeters of wrapping paper is a 10x10x10 cube with the volume 1000 cubic centimeters. Wrapping this box consumes 600 cm^2 of wrapping paper. This leaves us with just 5 cm^2 left, and that isn't enough to wrap any valid box.366
Returns: 451
The best box we can wrap is 7x8x8 (volume 448, surface area 352). Once we do that, we have 14 cm^2 of wrapping paper left. The best use for that paper is to wrap another 1x1x3 box (volume 3, surface area 14). Total volume of presents: 448 + 3 = 451.887
Returns: 1734
First we wrap a 12x12x12 cube, spending 6*12*12 = 864 cm^2 of wrapping paper. With the 23 cm^2 of paper left we select and wrap a 1x2x3 box. This requires 22 cm^2 of wrapping paper, and the remaining 1 cm^2 is already useless. Total volume is 12*12*12 + 1*2*3 = 1728 + 6 = 1734.888
Returns: 1728
Here we have 1 cm^2 more than in the previous example. What changes? As before, the volume of the first box we'll choose will be 1728. However, now there are multiple such boxes, and remember that in such a case we minimize the length of the shortest side. Hence, the selected box will be a 9x12x16 box instead of the 12x12x12 box. The surface area of this box is exactly 888 cm^2, so we'll spend all our wrapping paper on it and there will be no additional boxes.