CubePacking
SRM 507 · 2010-11-01 · by ir5
Problem Statement
Fox Ciel has Ns cubes with edge length 1 and Nb cubes with edge length L. She wants to pack her cubes in a rectangular parallelepiped box. Each cube must be packed in the box such that each of its edges is parallel to an edge of the box.
Ciel wants to know the smallest possible box she can use. Return the minimum possible volume of a box which can store her cubes.
Notes
- A rectangular parallelepiped is a closed box composed of three pairs of rectangular faces placed opposite each other and joined at right angles to each other.
- The answer will fit in 32-bit signed integer.
Constraints
- Ns will be between 1 and 1,000,000,000, inclusive.
- Nb will be between 1 and 1,000,000, inclusive.
- L will be between 2 and 10, inclusive.
2 2 2 Returns: 20
Ciel has two 1x1x1 cubes and two 2x2x2 cubes. She can pack them into 2x2x5 box. The volume of this box is 20.
19 1 2 Returns: 27
Ciel's cubes can be packed into 3x3x3 box. Its volume is 27.
51 7 5 Returns: 950
12345 987 10 Returns: 999400
1000000000 1000000 10 Returns: 2000000000
full power
158846335 973328 9 Returns: 868402447
wrongA will get "failed" by this case
87549617 866889 10 Returns: 954438617
even x=[1,5000], y=[1,5000] is not enough for seach range
148880604 739785 10 Returns: 888665604
some countercases (#7-#13)
411280731 999100 10 Returns: 1410380731
strong test; X,Y,Z > 1100 is required
995616979 1000000 10 Returns: 1995616979
very strong test; X,Y,Z>1256 is required
Submissions are judged against all 197 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CubePacking with a public method int getMinimumVolume(int Ns, int Nb, int L) · 197 test cases · 2 s / 256 MB per case