Presents2023
SRM 844 · 2023-01-19 · by misof
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.
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.
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.
9999992703231 Returns: 2151654948210946054
highest btotal found
9698643506776 Returns: 2055130706279639673
highest spread
9756552636909 Returns: 2073564471501180517
highest leftover
9838826748753 Returns: 2099848323011202508
highest leftover unequal bc
9927959240577 Returns: 2128447463576416043
highest leftover unequal ab
8862426387728 Returns: 1795154995533370787
highest max_at_once
Submissions are judged against all 132 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Presents2023 with a public method long long pack(long long paperArea) · 132 test cases · 2 s / 256 MB per case