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.
Definition
- Class:
- CubePacking
- Method:
- getMinimumVolume
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int getMinimumVolume(int Ns, int Nb, int L)
- (be sure your method is public)
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.
Examples
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)
80302604
397195
10
Returns: 477497604
64467984
635963
10
Returns: 700430984
144296168
978414
7
Returns: 479892170
77804954
940614
9
Returns: 763512560
44813785
687136
8
Returns: 396627417
241750556
940748
8
Returns: 723413532
185496388
924020
10
Returns: 1109516388
884755356
1000000
8
Returns: 1396755360
958268793
1000000
8
Returns: 1470268800
914241600
1000000
9
Returns: 1643241600
961809120
1000000
9
Returns: 1690809120
745944200
1000000
10
Returns: 1745944200
837836000
1000000
10
Returns: 1837836000
862340476
1000000
10
Returns: 1862340480
889727838
1000000
10
Returns: 1889727840
989187200
1000000
10
Returns: 1989187200
301
735134
10
Returns: 735134400
701
821620
10
Returns: 821620800
201
931170
10
Returns: 931170300
501
994593
10
Returns: 994593600
503
994593
10
Returns: 994593600
1
1
2
Returns: 12
3
4
2
Returns: 36
5
7
2
Returns: 64
9
10
2
Returns: 92
1
1
3
Returns: 36
3
4
3
Returns: 117
5
7
3
Returns: 198
9
10
3
Returns: 279
1
1
4
Returns: 80
3
4
4
Returns: 272
5
7
4
Returns: 464
9
10
4
Returns: 656
1
1
5
Returns: 150
3
4
5
Returns: 525
5
7
5
Returns: 900
9
10
5
Returns: 1275
17
15
3
Returns: 423
15
15
3
Returns: 423
15
15
3
Returns: 423
9
12
2
Returns: 108
4
4
5
Returns: 525
17
882
10
Returns: 882100
3
880
6
Returns: 190116
4
443
5
Returns: 55400
17
151
10
Returns: 151100
14
885
10
Returns: 885100
970
108
6
Returns: 24300
1315
228
7
Returns: 79527
1585
265
9
Returns: 194805
803
121
5
Returns: 15950
1371
197
6
Returns: 43956
400
725055
9
Returns: 528565500
379
804997
9
Returns: 586843218
282
737188
9
Returns: 537410376
82
692939
9
Returns: 505152693
306
521732
9
Returns: 380342952
669515080
64
9
Returns: 669561736
844185714
186
10
Returns: 844371715
950316674
232
9
Returns: 950485806
829708064
29
10
Returns: 829737064
990536539
79
9
Returns: 990594130
1
1000000
10
Returns: 1000000100
999999901
1000000
10
Returns: 1999999901
167730
869019
2
Returns: 7119882
118174
968711
2
Returns: 7867862
4151482
869021
5
Returns: 112779108
2484853
968712
5
Returns: 123573855
15862062
869018
8
Returns: 460799278
9515102
968712
8
Returns: 505495647
18286709
997037
10
Returns: 1015323710
28284720
997763
10
Returns: 1026047724
15341038
998941
10
Returns: 1014282040
17203816
998812
10
Returns: 1016015819
72826905
999596
10
Returns: 1072422908
9170969
998715
10
Returns: 1007885970
75202299
999947
10
Returns: 1075149300
14147142
997688
10
Returns: 1011835143
41286366
999647
10
Returns: 1040933370
15234487
997773
10
Returns: 1013007490
62794643
999306
10
Returns: 1062100643
53252183
980100
10
Returns: 1033352183
53252177
980100
10
Returns: 1033352183
73381457
970200
10
Returns: 1043581457
72069673
979608
10
Returns: 1051677673
11797734
998688
10
Returns: 1010485734
15379504
959136
10
Returns: 974515504
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
1518941
999999
10
Returns: 1001518000
7
902778
10
Returns: 902778100
1
999190
10
Returns: 999190100
1631310
997969
5
Returns: 126377440
861860
999972
4
Returns: 64860075
659203
506792
8
Returns: 260136720
7076
318
7
Returns: 116172
1239
3
10
Returns: 4290
498108
660735
10
Returns: 661233160
974932
998158
9
Returns: 728632170
945702
493482
10
Returns: 494427780
424242424
42
10
Returns: 424284425
999999999
999999
10
Returns: 1999998999
1000000000
559321
7
Returns: 1191847103
1000000000
1000000
2
Returns: 1008000000
1000000000
1
2
Returns: 1000000008
999999927
1000000
10
Returns: 1999999929
973929286
959492
10
Returns: 1933421290
708293742
6
10
Returns: 708299745
367431778
990001
7
Returns: 707002121
3003001
1000000
10
Returns: 1003003001
898653117
1000000
10
Returns: 1898653117
28
4
2
Returns: 60
324932
924789
9
Returns: 674496153
540470871
279874
10
Returns: 820344871
200010
1000000
10
Returns: 1000200010
987464534
999999
10
Returns: 1987463534
999999888
1000000
10
Returns: 1999999888
999999999
999999
7
Returns: 1342999656
994007910
1
10
Returns: 994008910
924325327
523425
8
Returns: 1192318928
1000000000
999998
9
Returns: 1728998544
987654
5432
9
Returns: 4947588
41429
12
8
Returns: 47575
810304731
1000000
9
Returns: 1539304731
33
1
3
Returns: 60
99999997
923591
7
Returns: 416791710
300030001
1000000
10
Returns: 1300030004
22191114
1
2
Returns: 22191122
562131235
121454
8
Returns: 624315684
7439143
999999
7
Returns: 350438803
456456223
62361
10
Returns: 518817223
999999915
1000000
10
Returns: 1999999915
901030507
1000000
10
Returns: 1901030508
9090910
909091
10
Returns: 918181935
981026972
1000000
10
Returns: 1981026972
36036009
444889
9
Returns: 360360090
58
2
2
Returns: 75
99999999
999999
7
Returns: 442999656
474192748
562458
6
Returns: 595683676
123456789
1000000
10
Returns: 1123456790
784770597
1000000
10
Returns: 1784770597
958645123
999999
10
Returns: 1958644125
42
2
3
Returns: 96
127
27
2
Returns: 343
102701599
1000000
10
Returns: 1102701600
669278610
1000000
10
Returns: 1669278610
800880234
1
2
Returns: 800880242
117
1
2
Returns: 125
14
2
2
Returns: 30
333
4
9
Returns: 3249
627100610
5
10
Returns: 627105610
25504074
1
2
Returns: 25504082
743755532
229290
10
Returns: 973045532
801280454
1
2
Returns: 801280462
1000000000
1000000
3
Returns: 1027000000
424504147
1000000
2
Returns: 432504147
19
1
3
Returns: 48
11741850
1
2
Returns: 11741858
999999729
27244
10
Returns: 1027243729
999999912
1000000
10
Returns: 1999999914
2000
2000
3
Returns: 56004
4072054
160000
5
Returns: 24072054
89
21
2
Returns: 258
677162373
1000000
10
Returns: 1677162373
874970314
64255
6
Returns: 888849395
456465
7897
8
Returns: 4499730
992441242
9789
10
Returns: 1002230242
10
1
2
Returns: 18
924911857
451660
5
Returns: 981369358
102701593
1000000
10
Returns: 1102701594
63236250
1
2
Returns: 63236258
999977
1
3
Returns: 1000004
912951531
1000000
10
Returns: 1912951531
9962
1
2
Returns: 9970
999999997
1000000
10
Returns: 1999999998
27243729
1000000
10
Returns: 1027243729
7761187
843900
10
Returns: 851661187
588558885
663601
9
Returns: 1072324014
13
2
2
Returns: 30
123456789
999997
10
Returns: 1123453791
1000000000
1
10
Returns: 1000001000
999999999
1
2
Returns: 1000000008
18
1
2
Returns: 27
57
1
3
Returns: 84
75908
1
2
Returns: 75916
295879057
685714
2
Returns: 301364769
900001133
1
2
Returns: 900001142
197410
974153
10
Returns: 974350410
978958785
987589
10
Returns: 1966547786