Problem Statement |
| | Introduction
Gears are discs with a number of teeth on them. The teeth of two gears interlock, and when one gear spins, the interlocked gear spins in the opposite direction. One common use of gears is to transfer forces at different speeds and torques. For instance, imagine gear A rotates at 10 revolutions per minute (RPMs) and has 20 teeth. Gear A drives gear B, which has only 10 teeth. Because of the way the teeth interlock, every revolution of gear A will result in gear B revolving twice, and thus B will revolve at 20 RPMs. In general the ratio of speeds is equal to the ratio of teeth, and the two gears rotate in opposite directions.
Your task in this problem is to achieve the largest decrease in speed possible, in the smallest space possible. You are to arrange the gears in K planes. Each gear requires an axle, which passes through all planes. Two gears centered at the same place on different planes will be considered to be attached to the same axle. Naturally, gears may not overlap the axle, unless they are fixed to it and may not overlap each other unless one drives the other. Gears in different planes should be thought of as having different Z coordinates, and so they cannot drive each other.
This image shows four gears. The two black gears are in one plane, and the two blue gears are in another. Note that two of the gears are on the same axle.
Details
A gear with T teeth has outer radius 10*T. The overlap between two gears with T1 and T2 teeth is 10*(T1+T2) minus the distance between their centers. In a particular plane, one gear drives another if their overlap is between 9 and 10, inclusive. If the overlap is greater than 10, or between 0 and 9 (exclusive), the configuration is invalid. Each gear requires an axle, which runs though all planes and has radius 10. Gears on different planes may be attached to the same axle if their centers are within 0.01 of each other.
Here is a simple example. The input is applied to an axle at (0,0). We put a gear with 10 teeth on this axle. This drives a gear with 20 teeth centered at (290,0). There is another gear with 12 teeth attached to the same axle at (290,0), in another plane. Finally, this gear drives a gear with 16 teeth centered at (290,270). If the first axle spins at a rate of 8 RPM, this drives the second axle at 4 RPM. This, in turn drives the third axle at 3 RPM (4 * 12 / 16). The direction changed twice, so the output direction is the same as the input direction.
You will be given a set of gears, described by the number of teeth each one has. You will also be given K, the number of planes available. your task is to use (almost) all of these gears in a way that minimizes the overall gearing ratio. The gears will be given to you in sorted order. Thus, you should use gears from the first half of the list to drive gears in the second half of the list. Your ratio must be minimized, but this means that you might omit a few gears from the very middle of the list, where the drive ratio would be 1:1. Your task is to minimize the area of the bounding box surrounding all the gears. You should output a String[], each element of which is formatted as "TEETH PLANE X Y", where PLANE is indexed from 0. X and Y are the coordinates of the gear's center, while TEETH is the number of teeth on the gear. Element 0 of your return should be on the input axle, while the last element should be on the output axle. The ordering of the other elements of your return does not matter.
Scoring
Your score for an individual test case will be the area of the bounding box enclosing all the gears. For each test case we will calculate (BEST/YOU)2, where BEST is the best score on that test case, and YOU is your score (your area). To compute your overall score, we'll sum this over all test cases.
Visualizer
A visualizer is provided to help you develop your solution. |
| |
Definition |
| | | Class: | Gearing | | Method: | place | | Parameters: | int, int[] | | Returns: | String[] | | Method signature: | String[] place(int K, int[] teeth) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The positioning of your gears may all be floating point values. For two gears to be considered to be on the same axle, they must have (x,y) coordinates within 0.01 (Euclidean distance). |
| - | teeth will be sorted. |
| - | In a valid configuration, the gear(s) on each axle will interlock with exactly two other gears, with the exception of the starting and ending axles, which will interlock with exactly one other gear. This will usually mean two gears on each axle, each of them interlocking with one other gear on a different axle. |
| - | Your output may rotate in either direction. |
| - | Notice that the maximum reduction in speed will be achieved by driving bigger gears with smaller gears. You will typically use the gears from the first half of the input to drive the gears in the second half of the input. In some cases you will be able to achieve the same reduction without using every gear, which is allowed. |
| - | The time limit is 30 seconds, and the memory limit is 1024MB. There are 100 provisional tests. |
| - | Gears are fixed to the axles they are on, and rotate at the same speed as the axle. |
| - | 64-bit floating point numbers will be used in the evaluation of your solution. You may want to leave slight tolerances to allow for this. |
| |
Constraints |
| - | The number of gears will be chosen as an even number uniformly between 10 and 100, inclusive. |
| - | An integer, M, will be chosen uniformly between 5 and 40, inclusive. |
| - | The number of teeth on each gear will be chosen uniformly between M and 50, inclusive. |
| - | The number of planes will be chosen uniformly between 3 and 6, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: "N = 24<br>
K = 4<br>
M = 39<br>
" | |
|
| 1) | |
| | | Returns: "N = 66<br>
K = 5<br>
M = 32<br>
" | |
|
| 2) | |
| | | Returns: "N = 98<br>
K = 3<br>
M = 18<br>
" | |
|
| 3) | |
| | | Returns: "N = 38<br>
K = 4<br>
M = 26<br>
" | |
|
| 4) | |
| | | Returns: "N = 40<br>
K = 5<br>
M = 19<br>
" | |
|
| 5) | |
| | | Returns: "N = 20<br>
K = 5<br>
M = 11<br>
" | |
|
| 6) | |
| | | Returns: "N = 38<br>
K = 5<br>
M = 11<br>
" | |
|
| 7) | |
| | | Returns: "N = 66<br>
K = 4<br>
M = 36<br>
" | |
|
| 8) | |
| | | Returns: "N = 68<br>
K = 4<br>
M = 15<br>
" | |
|
| 9) | |
| | | Returns: "N = 26<br>
K = 3<br>
M = 36<br>
" | |
|
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)2020, TopCoder, Inc. All rights reserved.