TopCoder problem "Driving" used in TCCC05 Round 2 (Division I Level Three)



Problem Statement

    With gasoline prices as they are, driving can be expensive. By always driving at the optimal speed, however, you can minimize the cost. To do this, you must take 3 factors into account.

1) The cost of your time. The faster you get where you are going, the more time you have to do other things.

2) The cost of speeding tickets. If you drive too fast, there is a risk that you will get a speeding ticket.

3) The cost of operating the vehicle (gasoline plus wear and tear).

You have collected some data pertaining to these three factors, and would now like to calculate the optimal speed to drive at. You will be given an int, costOfTime, representing the price at which you value an hour of your time. You will be given a String[], tickets, indicating the cost and likelihood of getting a ticket at various speeds. Finally, you will be given a String[], costPerMile, indicating the cost of operating your vehicle at different speeds.



Each element of tickets will be formatted as "SPEED PROBABILITY COST", indicating the probability per mile of receiving a ticket when travelling at the given speed. If you are travelling at a speed that does not correspond to any element of tickets, you should use linear interpolation to determine the probability of receiving a ticket (see examples). However, the cost of the ticket will be the cost of the ticket for the highest speed less than or equal to the travel speed. Note that if you are travelling at a speed less than the minimum SPEED in tickets, you cannot receive a ticket. Also, you should assume that each mile of road is independent and if you receive a ticket during one mile, that does not affect the probability of receiving a ticket during the next mile. Furthermore, you should assume that you will not receive more than one ticket in a single mile.



Each element of costPerMile will be formatted as "SPEED COST" indicating the cost per mile of travelling at a given speed. You should again interpolate to find the cost of speeds not in costPerMile. Your car cannot travel faster than the highest SPEED in costPerMile, and the smallest SPEED in costPerMile will always be 0.



You should find the speed that gives the lowest expected cost per mile and return that cost.
 

Definition

    
Class:Driving
Method:lowestCost
Parameters:int, String[], String[]
Returns:double
Method signature:double lowestCost(int costOfTime, String[] tickets, String[] costPerMile)
(be sure your method is public)
    
 

Notes

-You need not worry about the time that it takes to receive and deal with a ticket as this is already factored into the costs given to you.
-Your return must have a relative or absolute error less than 1E-9.
 

Constraints

-costOfTime will be between 1 and 1000, inclusive.
-tickets will contain between 1 and 50 elements, inclusive.
-costPerMile will contain between 2 and 50 elements, inclusive.
-Each element of tickets and costPerMile will contain at most 50 characters.
-Each element of tickets will be formatted as "SPEED PROBABILITY COST".
-Each element of costPerMile will be formatted as "SPEED COST".
-Each SPEED in both inputs will be between 0 and 200, inclusive.
-Each PROBABILITY will be between 0 and 0.1, inclusive.
-Each COST in tickets will be between 1 and 1000000, inclusive.
-Each COST in costPerMile will be between 0 and 5, exclusive.
-All numbers in the inputs will be formatted as sequences of 1 or more digits, with an optional decimal point. They may contain extra leading or trailing zeros.
-The smallest SPEED in costPerMile will be 0.
-The largest SPEED in tickets will be greater than or equal to the largest SPEED in costPerMile.
-Both String[] inputs will be sorted in ascending order by SPEED.
-tickets will be sorted in non-descending order by COST and PROBABILITY.
-No two SPEEDS in costPerMile will be within 1 of each other.
-No two SPEEDS in tickets will be within 1 of each other.
 

Examples

0)
    
50
{"80 0.001 100"}
{"0 0.01","30 0.40","55 0.37","65 0.42","75 0.53"}
Returns: 1.1882396974191325
At 67.42 miles per hour, the cost of operating the vehicle is found by linear interpolation. That is, imagine drawing a straight line from (65,0.42) to (75,0.53). Then, find the y-value of the point on this line corresponding to x = 67.42. That is the cost per mile of operating the vehicle (0.44662 here). In this case, there are no tickets, so we need not worry about that. The cost of the time is 0.74162 per mile, for a total of 0.44662+0.74162 = 1.18824.
1)
    
50
{"60 0.00001 50","65 0.00003 70","70 0.0001 110","75 0.001 180"}
{"0 0.01","30 0.40","55 0.37","65 0.42","75 0.53"}
Returns: 1.1907307692308355
In this case, there is some risk of getting a ticket. The cheapest speed is just a hair under 65 so that you only have to pay 50 if you get a ticket.
2)
    
100
{"60 0.00001 50","65 0.00003 70","70 0.0001 110","75 0.001 180"}
{"0 0.01","30 0.40","55 0.37","65 0.42","75 0.53"}
Returns: 1.9105714285715127
Same as example 1, but with a higher value on time.
3)
    
1000
{"60.50 0.00002 50.53","65 0.00007 70",
 "070 0.0002 150","75 0.002 200",
 "080.001 0.004 300","85. 0.004 1000000",
 "150 0.004 1000000"}
{"0 0.50","30 0.40","55.5 0.37","65 0.42","75 0.63","80 0.87","95 1.30"}
Returns: 13.978039215687371

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6529&pm=3501

Writer:

lars2520

Testers:

PabloGilberto , lbackstrom , Yarin , vorthys

Problem categories:

Math, Search