SquareWashers | Topcoder Archive

Problem Statement

The engineers at Square Washers, Inc., need to improve production efficiency in order to catch up to their competition. Currently, whenever they make their square washers, they start with a rectangular prism of steel, choose an orientation for the washers (along the XY plane, XZ plane, or YZ plane), and chop away, hoping for the best. However, someone recently realized that one of these three planes of orientation may yield better results than the others. In addition, the remaining steel can be used to make more washers. Now, they need to figure out an algorithm to produce the most washers out of one rectangular prism. For the purposes of this problem, a rectangular prism is a 3-dimensional geometric shape with six sides, such that the angle between any two adjacent edges is a right angle.

Since these washers are square, and (for purposes of efficiency) since they don't care about the inside diameter, for all intents and purposes in this problem, a square washer may be treated as a rectangular prism of which at least two dimensions are equal. Further, once it is decided which plane to cut the washers on, as many washers as can be cut in that plane must be cut in that plane. For instance, if the block of steel was 7 x 11 x 3, and the washer size was 3 x 3 x 1 (diameter of 3, thickness of 1) (dimensions given in X x Y x Z order), and the plane used was the XY plane, then 18 washers would be cut in this plane (2 in the X dimension, 3 in the Y dimension, and 3 in the Z dimension). It would be illegal to cut less than 2 in the X dimension, less than 3 in the Y dimension, or less than 3 in the Z dimension.

You will be given the width, height, and depth of the block of steel, as well as the diameter and thickness of the washers that need to be produced. For purposes of this problem, assume the saw blades used are infinitesimally thin. You are to determine the maximum number of washers that can be produced.

In addition to reusing the remaining steel from the initial cutting, the remaining steel from each additional cutting should be used, until no more washers can be made from the remaining steel.

Definition

Class:: SquareWashers
Method:: howMany
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long howMany(int wide, int high, int deep, int diameter, int thickness)
(be sure your method is public)

Constraints

high will be between 1 and 10000, inclusive.
wide will be between 1 and 10000, inclusive.
deep will be between 1 and 10000, inclusive.
diameter will be between 1 and 10000, inclusive.
thickness will be between 1 and 10000, inclusive.
thickness will be less than or equal to diameter.

Examples

```
7
```
```
11
```
```
3
```
```
3
```
```
1
```
```
Returns: 25
```
The best solution is to cut initially in the XZ plane. This gives us 2 washers in the X dimension, 1 in the Z dimension, and 11 in the Y dimension for a total of 22 washers. The remaining block of steel is 1 x 11 x 3 units, which will yield an additional 3 washers by cutting in the YZ plane. Adding together, we get 22 + 3 = 25.
```
5
```
```
11
```
```
7
```
```
3
```
```
2
```
```
Returns: 17
```
Cutting in the XY plane yields 9 washers. Cutting the remainder first in the YZ plane yields an additional 6, and the remainder of this again in the XZ plane yields 2 more washers. The total is 9 + 6 + 2 = 17.
```
57
```
```
67
```
```
37
```
```
11
```
```
3
```
```
Returns: 372
```
```
7392
```
```
4247
```
```
266
```
```
630
```
```
34
```
```
Returns: 462
```
```
1546
```
```
6742
```
```
456
```
```
17
```
```
5
```
```
Returns: 3278808
```
```
123
```
```
457
```
```
789
```
```
457
```
```
124
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.