Problem Statement
Note to plugin users: There are images in the problem statement and examples. Please use the applet to view them.
You have a piece of wood that you want to use to make the walls of a box that holds jars (shaped as perfect cylinders). The piece of wood is one jar height wide, and the resulting box will only hold one layer of jars. The jars will be placed upright in the box. In order to make the walls of the box, you need to cut the wood into four separate pieces. Each piece needs to be cut such that the four pieces attached at the ends form a rectangle.
To minimize the stress on each jar, you want to pack the jars into the box as tightly as possible, so they are touching as many other jars as possible. The jars in a single row must be horizontally adjacent to each other. However, each successive row must be skewed one radius such that the jars sit exactly between two jars from the previous row to form a hexagonal pattern (Note that this may not be the most efficient space-wise). Here is an example (as viewed from above):
Given the radius, in inches, of the jars that you would like to store, and the woodlength in inches, return the maximum number of jars you can store in a box whose perimeter is at most woodlength inches.
Definition
- Class:
- JarBox
- Method:
- numJars
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int numJars(int radius, int woodlength)
- (be sure your method is public)
Notes
- The box dimensions do not have to be integers
- Even if it is possible to fit more jars in by placing jars so that adjacent rows are not skewed, this is not a legal arrangement of the jars.
Constraints
- radius will be between 1 and 10, inclusive.
- woodlength will be between 8 and 10000, inclusive.
- For all possible boxes that contain more than one row of jars, the optimal length of wood required will be at least .000001 inches smaller than the woodlength given.
- It will be possible to store at least one jar using the woodlength given.
Examples
1
8
Returns: 1
The smallest box for the given radius. Only one jar barely fits into the box.
1
16
Returns: 3
There are two ways to get 3 jars in this box. First, you could have one row of 3 jars. Another way is to have two rows, one row of 2 jars, and one row of 1 jar like so: Note that although it would be more efficient to store the jars in a square pattern, this is not allowed.
1
18
Returns: 4
In order to fit 4 jars in this box, the width must be 5, and the rows both contain 2 jars each. The following diagram shows how the jars will sit:
1
45
Returns: 32
If we make the box 10 inches wide, it will fit exactly 5 jars across on the odd rows (starting with the bottom), and 4 jars across on all the even rows. This will allow us to create 4 rows of 5 jars across, and 3 rows of 4 jars across. The optimal dimensions of the box will be about 10 x 12.392305.
1
10000
Returns: 1803252
6
1269
Returns: 784
10
8544
Returns: 13082
7
8840
Returns: 28640
10
4480
Returns: 3575
8
603
Returns: 95
3
2081
Returns: 8613
3
2685
Returns: 14365
7
695
Returns: 168
4
8235
Returns: 76258
1
7968
Returns: 1144706
4
7805
Returns: 68495
7
1511
Returns: 816
3
8305
Returns: 138006
4
6838
Returns: 52553
7
2827
Returns: 2900
10
7760
Returns: 10792
6
2100
Returns: 2175
3
5609
Returns: 62879
3
5506
Returns: 60588
2
4903
Returns: 108195
7
545
Returns: 100
8
2562
Returns: 1817
3
3307
Returns: 21816
10
4331
Returns: 3339
8
8732
Returns: 21390
2
3753
Returns: 63350
7
9823
Returns: 35394
4
7794
Returns: 68320
10
3656
Returns: 2376
10
2168
Returns: 825
2
3501
Returns: 55118
5
2702
Returns: 5214
2
4227
Returns: 80388
7
8354
Returns: 25578
6
5143
Returns: 13176
10
7383
Returns: 9765
10
9737
Returns: 17010
10
8611
Returns: 13293
7
2946
Returns: 3150
10
1287
Returns: 285
1
4364
Returns: 343202
3
6044
Returns: 73041
7
1140
Returns: 462
8
6523
Returns: 11918
3
8120
Returns: 131920
2
3807
Returns: 65176
1
8
Returns: 1
2
517
Returns: 1178