TopCoder problem "WinningTrick" used in TCHS SRM 4 (Division I Level One)



Problem Statement

    

You will be running a race on a straight track, and you have devised the following trick to help you win. The weather forecast for the day of the race indicates that there will be a strong wind blowing directly from the finish line to the starting line. You ask the judges to allow you to run the race backward from the finish line to the starting line, and since they are unaware of your motives, they allow you to do so.

All participants, including you, will run at a constant speed for the duration of the race. Your competitors' speeds are given in the int[] speed, each element of which represents the speed of a competitor in meters per second. Your own speed in meters per second is given in the int yourSpeed.

The wind will blow at a constant speed of W meters per second. It will therefore increase your speed by W meters per second while decreasing the speed of each of your competitors by W meters per second. Return the minimum value of W that will allow you to win the race. Return 0.0 if you can win without the help of any wind. You will win the race even if you tie for first place.

 

Definition

    
Class:WinningTrick
Method:minimumSpeed
Parameters:int[], int
Returns:double
Method signature:double minimumSpeed(int[] speed, int yourSpeed)
(be sure your method is public)
    
 

Notes

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

Constraints

-speed will contain between 1 and 50 elements, inclusive.
-Each element of speed will be between 1 and 10, inclusive.
-yourSpeed will be between 1 and 10, inclusive.
 

Examples

0)
    
{4, 3, 2, 1}
5
Returns: 0.0
Here you are the fastest runner, so you don't need any wind to win the race.
1)
    
{3, 3}
3
Returns: 0.0
If there is no wind, then all the runners will tie for first place. As stated in the problem statement, you will win the race in this situation.
2)
    
{2, 3, 4, 5}
1
Returns: 2.0
If the wind's speed is 2.0 m/s, then your speed will be 3.0 m/s and speeds of your opponents will be 0.0 m/s, 1.0 m/s, 2.0 m/s, and 3.0 m/s. That is enough for you to tie for first place. Lower wind speeds will not allow you to win the race.
3)
    
{9}
1
Returns: 4.0
4)
    
{1, 1, 2, 2, 5, 2}
3
Returns: 1.0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10023&pm=6421

Writer:

ivan_metelsky

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Math, Simple Search, Iteration