TopCoder problem "JarBox" used in SRM 162 (Division I Level Two)



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

0)
    
1
8
Returns: 1
The smallest box for the given radius. Only one jar barely fits into the box.
1)
    
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.

2)
    
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:

3)
    
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.
4)
    
6
1269
Returns: 784

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1586

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4615&pm=1586

Writer:

schveiguy

Testers:

lbackstrom , brett1479

Problem categories:

Geometry