TopCoder problem "HighwayJam" used in TCHS SRM 31 (Division I Level Two)



Problem Statement

    

It's only 9 AM, and already your day has been horrible. You overslept your alarm, your oatmeal got cold as you listened to the traffic report, and the water in your shower was frigid. To make matters worse, as you got onto the highway you saw a horrible traffic jam. To try to make your day better, you have to figure out the fastest way to get to your exit.

You have been given lanes, a int[] listing the speed (in feet per second) of cars traveling in each lane on the highway. You begin in lane 0, and your exit (located dist feet away) is also in lane 0. You are allowed to move into an adjacent lane only if you have been in your current lane for at least laneChange seconds; otherwise, you won't have sufficient time to make sure there's no accident! This also includes exiting; if you change lanes during your trip, you must return in lane 0 for at least laneChange seconds in order to safely exit the highway. If you do not change lanes during your trip, then you may exit the highway as soon as you reach your exit.

With this information, return the least amount of time required for you to reach your exit. See the examples for further clarification.

 

Definition

    
Class:HighwayJam
Method:minTime
Parameters:int[], int, int
Returns:double
Method signature:double minTime(int[] lanes, int laneChange, int dist)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-lanes will contain between 1 and 50 elements, inclusive.
-Each element of lanes will be between 0 and 528000, inclusive.
-Element 0 of lanes will not be 0.
-laneChange will be between 0 and 60, inclusive.
-dist will be between 0 and 1000000000 (109), inclusive.
 

Examples

0)
    
{1,2}
2
15
Returns: 9.5
In this case, you can stay in lane 0, which will take you 15/1 = 15 seconds. Alternatively, you can shift into lane 1 after 2 seconds, drive for 5.5 seconds, and then switch back to lane 0 for 2 more seconds. This covers 2(1) + 5.5(2) + 2(1) = 15 feet in only 9.5 seconds.
1)
    
{1, 2}
2
6
Returns: 6.0
Here, you do not have enough time to safely switch to the other lane and come back, so you must stay in lane 0 the whole time.
2)
    
{528000}
10
1
Returns: 1.893939393939394E-6
3)
    
{1, 0, 10}
4
1000
Returns: 115.2
The middle lane is not moving at all, but you need to pass through it to get to the fastest lane.
4)
    
{12, 0, 18, 0, 0, 0, 0,
 944, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 528000}
15
1500
Returns: 123.33333333333334

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10655&pm=7374

Writer:

connect4

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simulation