CogWheel | Topcoder Archive

Problem Statement

You are building an experimental car transmission by connecting successive cogwheels. Your boss wants you to assemble the wheels for the greatest possible speed. For this task, you must assemble a succession of wheels, each one driving the next one, so that the ratio between the first and last wheels is the maximum possible. Your boss allows you use as many wheels as you need, with only one constraint: the ratio of rotation between adjacent wheels cannot be greater than 2.0 (he thinks wheel teeth break easily if differences in wheel sizes are greater than this number).

Take for example, the following wheel set, where the annotation in the wheels indicate their number of teeth:

Each spin of the first wheel will spin the second wheel 18/16=1.125 times, each spin of the second wheel will spin the third wheel 16/20=0.8 times, and each spin of the third wheel will spin the last wheel 20/12 times. Thus, for each spin of the first wheel the last one spins 1.5 times, and this is the speed ratio of the assembled set. Note that by ordering the wheels in a different way (or using just the last two wheels), a ratio of 5/3=1.66666 can be obtained.

The int[] wheels specifies the number of teeth in each of the available wheels. You are to return the maximum ratio of speed between first and last wheels. If no transmission can be assembled, return 1.0.

Definition

Class:: CogWheel
Method:: maximumSpeed
Parameters:: int[]
Returns:: double
Method signature:: double maximumSpeed(int[] wheels)
(be sure your method is public)

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

wheels will contain between 1 and 20 elements, inclusive.
All elements in wheels will be between 1 and 100, inclusive.

Examples

{12,18,16,20}

Returns: 1.6666666666666667

The example from the statement.

```
{10,20}
```
```
Returns: 2.0
```
Using the 20-teeth wheel to move the 10-wheel makes the second wheel rotate twice as fast as the first wheel.
```
{21,12,8}
```
```
Returns: 2.625
```
All wheels in succession can give the amazing rotation ratio of 2.625.
```
{1,2,4,10,20,40,80}
```
```
Returns: 8.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.