Problem Statement |
| | If a runner races a distance D in time T, and later races a distance 2D, that runner will likely take more than 2T time to finish it. An examination of how times change with distances for a given runner can lead to the following approximation for the time it will take that runner to finish a given distance. Given two races with distances D1 and D2 (D1<D2) which a runner ran in times T1 and T2 (T1<T2) , respectively, the approximate time it will take a runner to run a distance D is given by:
T1*e^(ln(T2/T1)*ln(D1/D)/ln(D1/D2)).
While it is clear which of a runner's races for a given distance is the best (the one that he or she ran the fastest), it isn't so clear what race is the best over all distances. This equation can help give an objective measure of that, however. If a runner has raced distances of D1...Dn, with corresponding times of T1...Tn, then any pair of two distances with their times will be able to approximate the rest of the times with the equation from above. Any other time will have a percent error from this approximation given by (actualTime-expectedTime)/expectedTime. Take the highest percent error for a time over all possible approximations, and this is that race's 'badness'. The race with the lowest badness is considered the best race.
Create a class RaceCalculator with a method bestRace that takes a int[] distances and a int[] times and returns an int that is the index of the best race specified by the input. Each value in distances will correspond to the value in times of the same index. All distances are in meters and all times are in seconds. |
| |
Definition |
| | | Class: | RaceCalculator | | Method: | bestRace | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int bestRace(int[] distances, int[] times) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | In C++ e^x can be done with exp(x), and the natural log, ln(x), can be done with log(x), both functions are in math.h. |
| - | In C# e^x can be done with Math.Exp(x), and the natural log, ln(x), can be done with Math.Log(x). The Math class is in the System namespace. |
| - | In Java e^x can be done with Math.exp(x), and the natural log, ln(x), can be done with Math.log(x). |
| - | In Visual Basic e^x can be done with Exp(x), and the natural log, ln(x), can be done with Log(x), both functions are in the System.Math namespace. |
| |
Constraints |
| - | distances and times will both contain between 3 and 50 elements, inclusive. |
| - | distances and times will contain the same number of elements. |
| - | Every element in distances and times will be between 1 and 100000, inclusive. |
| - | No value in distances will occur more than once. |
| - | If the i-th value in distances is less than the j-th value in distances, then the i-th value of times will be less than the j-th value of times. |
| - | To avoid rounding issues, no two races' badnesses will be within 1e-9 of each other. |
| - | To make the approximation reliable, all speeds (distance/time), including those generated by the approximation, will be between 0.1 meter/second and 100 meters/second, inclusive. |
| |
Examples |
| 0) | |
| | {1600,3200,16000} | {299,655,4020} |
| Returns: 2 | | This person runs 1.6 km in 4:59, 3.2 km in 10:55, and 16 km in 1:07:00. The expected times for each distance (always using the approximation based on the results of the other two races) are about 4:59.8 for the 1.6 km, 10:53.7 for the 3.2 km, and 1:07:26.0 for the 16 km. This results in badnesses of roughly -0.002767 for the 1.6 km, 0.001939 for the 3.2 km, and -0.006414 for the 16 km. |
|
|
| 1) | |
| | {1600,2000,3200,3000,5000,9600} | {234,306,499,462,802,1629} |
| Returns: 3 | Steve Prefontaine was probably the best American runner of all time. Here are his times for the 1.6 km, 2 km, 3 km, 3.2 km, 5 km, and 9.6 km. The badnesses of the respective races are about:
{0.0727,0.0747,0.0115,0.003,0.033,0.081} |
|
|
| 2) | |
| | {1000,2000,3000,4000} | {160,330,510,750} |
| Returns: 2 | |
|
| 3) | |
| | {1000,50000,10000,5000} | {200,70010,2250,1080} |
| Returns: 2 | |
|