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.
9999992703231
Returns: 2151654948210946054
highest btotal found
9999828300486
Returns: 2151601838049369192
9999756726380
Returns: 2151578505269770530
9698643506776
Returns: 2055130706279639673
highest spread
9307071000585
Returns: 1931934913164043900
9756552636909
Returns: 2073564471501180517
highest leftover
9879236179718
Returns: 2112798148423229880
9838826748753
Returns: 2099848323011202508
highest leftover unequal bc
9927959240577
Returns: 2128447463576416043
highest leftover unequal ab
8862426387728
Returns: 1795154995533370787
highest max_at_once
9030655608690
Returns: 1846511386448027136
9778037965061
Returns: 2080417853988411820
37
Returns: 12
38
Returns: 12
201
Returns: 181
202
Returns: 180
6
Returns: 1
11
Returns: 2
12
Returns: 2
444
Returns: 616
467
Returns: 652
509
Returns: 735
4718803
Returns: 697082247
255999072
Returns: 278690969891
104554406420
Returns: 2300306349787954
5955217264
Returns: 31269031444672
550195858414
Returns: 27768270864865935
128654
Returns: 3133602
1945526
Returns: 184544980
24174
Returns: 254088
15092312079
Returns: 126155303467920
398384431
Returns: 541011420894
404568667768
Returns: 17508986040611357
2507971
Returns: 270069516
14823990
Returns: 3882268237
5380883297
Returns: 26856352241940
3158239170747
Returns: 381891845468694141
1310277910
Returns: 3227138452826
55499601715
Returns: 889624402209604
4530769
Returns: 656148009
1744200488
Returns: 4956353951682
123607717077
Returns: 2956923977896281
94494
Returns: 1969002
390160982005
Returns: 16582059944327558
33064496
Returns: 12933765584
85092
Returns: 1685249
276590639
Returns: 312977719495
1193
Returns: 2748
6643732625
Returns: 36845914546480
232351988
Returns: 240982775273
7815141
Returns: 1486343250
1500396267
Returns: 3954306328950
10275110721
Returns: 70868030997402
247443
Returns: 8365595
76123533
Returns: 45187827048
8736258
Returns: 1756955070
71002
Returns: 1283273
11026628440
Returns: 78783321531604
1202019997459
Returns: 89668561560936384
962335677241
Returns: 64233695533798785
42677
Returns: 599760
41106422055
Returns: 567068380007137
8643892091380
Returns: 1729167414843552171
9789702421419
Returns: 2084142246450464262
7271871815957
Returns: 1334266037794502321
6220906420673
Returns: 1055731419063390540
5329653300293
Returns: 837185114398861152
8606082488578
Returns: 1717834600603051932
2459288227741
Returns: 262414019114883580
2059470643596
Returns: 201097337537996357
8117072847107
Returns: 1573519499715959752
7645118572277
Returns: 1438299939198409059
9920557010579
Returns: 2126067632407537545
1168086444794
Returns: 85898436097201887
8623026269939
Returns: 1722910285349546818
2007907496283
Returns: 193592406660327576
4315389660499
Returns: 609962314622928512
2934884769294
Returns: 342105059538562896
397123676994
Returns: 17027904949058239
1729101105378
Returns: 154704716001350928
8081715134728
Returns: 1563249323724732636
8104344290927
Returns: 1569819825861002836
4870395171702
Returns: 731340159589255823
9584812364412
Returns: 2019056396911427820
3331005690617
Returns: 413652937646245441
718492429936
Returns: 41438718707040723
4633289621396
Returns: 678589620719994062
9530609936368
Returns: 2001954185512176896
9074662437551
Returns: 1860024572149109065
9866391206142
Returns: 2108679540337218190
9966835942117
Returns: 2140962342187393189
9779626170672
Returns: 2080924723356610888
9659664011268
Returns: 2042754303844014000
9590460587123
Returns: 2020841294950144292
9870780278032
Returns: 2110086440632592644
9637209777343
Returns: 2035635367908690137
9452310294578
Returns: 1977333713236315971
9750631384170
Returns: 2071677151915292844
9987396311570
Returns: 2147590678770582553
9804038793592
Returns: 2088721860272444700
9101500890993
Returns: 1868282473990896940
9563081725738
Returns: 2012193632031455794
9338482607364
Returns: 1941723819348985451
9589839694332
Returns: 2020644869407591844
9398728625199
Returns: 1960544456325368114
9119619534662
Returns: 1873864208750833333
9936703077442
Returns: 2131259967868115073
9818717083008
Returns: 2093413762942098210
9396967191407
Returns: 1959993559834417808
9382467889930
Returns: 1955458741506403979
9951691023728
Returns: 2136084559427596036
9697467716754
Returns: 2054757329973635905
52
Returns: 24
53
Returns: 24
408
Returns: 540
409
Returns: 540
7529453509603
Returns: 1405782464754153604
9245816517147
Returns: 1912894059879767302
10000000000000
Returns: 2151656837709465621
8929383040014
Returns: 1815537241997378932
9999999999999
Returns: 2151656837709465621
8797568847491
Returns: 1775484828972090628
9757419806901
Returns: 2073840927110169717
9794319252364
Returns: 2085615947259723074
2504803960031
Returns: 269732640504379514
8726349857628
Returns: 1753969326235459516
333
Returns: 394
14095968537
Returns: 113870692680896