TopCoder problem "RoadOrFlightEasy" used in Member SRM 468 (Division II Level One)



Problem Statement

    The king has been out to work for a long time and he wants to go back to his queen as fast as possible. The king is in city 0 and the queen is in city N. There are roads and flights connecting city i to city (i+1) for all i between 0 and N-1, inclusive.



You are given int[] roadTime whose i-th element is the time it takes to travel from city i to city (i+1) by road and int[] flightTime whose i-th element is the time it takes to travel from city i to city (i+1) by flight. However, taking a flight risks the life of the king due to the technological limitations in the kingdom. Hence the queen has asked the king to take at most K flights on his way.



Return the minimum amount of time in which the king can reach his queen.

 

Definition

    
Class:RoadOrFlightEasy
Method:minTime
Parameters:int, int[], int[], int
Returns:int
Method signature:int minTime(int N, int[] roadTime, int[] flightTime, int K)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 50, inclusive.
-roadTime will contain exactly N elements.
-flightTime will contain exactly N elements.
-Each element of roadTime and flightTime will be between 1 and 1000, inclusive.
-K will be between 0 and N, inclusive.
 

Examples

0)
    
3
{4, 6, 7}
{1, 2, 3}
1
Returns: 13
All flightTimes here are less than roadTimes. However the king can choose only 1 flight. The are two possible optimal routes. City 0-->1, 1-->2 by road and 2-->3 by flight takes time 4 + 6 + 3 = 13 units. City 0-->1 by road, 1-->2 by flight and 2-->3 by road also takes time 4 + 2 + 7 = 13 units.
1)
    
3
{4, 6, 7}
{1, 2, 3}
2
Returns: 9
Now the king is allowed to take 2 flights.
2)
    
3
{4, 6, 7}
{1, 2, 3}
3
Returns: 6
Choose all 3 flights since flights are faster than roads.
3)
    
3
{1, 2, 3}
{2, 3, 4}
2
Returns: 6
flightTime can be larger than roadTime. So the King may take fewer than K flights even though he is allowed to take K of them.
4)
    
7
{50, 287, 621, 266, 224, 68, 636}
{797, 661, 644, 102, 114, 452, 420}
2
Returns: 1772

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14183&pm=10764

Writer:

keshav_57

Testers:

Rustyoldman , ivan_metelsky , mohamedafattah , it4.kp

Problem categories:

Sorting