Connection Status:
Competition Arena > RoadOrFlightEasy

RoadOrFlightEasy

Member SRM 468 · 2009-12-03 · by keshav_57

Member SRM 468 · 2009-12-03 · by keshav_57 · Sorting
Class Name: RoadOrFlightEasy
Return Type: int
Method Name: minTime
Arg Types: (int, vector<int>, vector<int>, int)
Problem Statement

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.

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)
1
{1000}
{1}
0
Returns: 1000

Submissions are judged against all 146 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RoadOrFlightEasy with a public method int minTime(int N, vector<int> roadTime, vector<int> flightTime, int K) · 146 test cases · 2 s / 256 MB per case

Submitting as anonymous