Connection Status:
Competition Arena > TravelOnMars

TravelOnMars

SRM 583 · 2012-12-13 · by blue.boy

SRM 583 · 2012-12-13 · by blue.boy · Search
Class Name: TravelOnMars
Return Type: int
Method Name: minTimes
Arg Types: (vector<int>, int, int)
Problem Statement

Problem Statement

Bob recently went to Mars.

There are N cities on Mars. The cities all lie on a circular railroad and they are numbered 0 through N-1 along the railroad. More precisely, there is a railroad segment that connects cities N-1 and 0, and for each i (0 <= i <= N-2) there is a railroad segment that connects cities i and i+1. Trains travel along the railroad in both directions.

You are given a int[] range with N elements. For each i: the set of cities that are reachable from city i by a direct train is precisely the set of cities that are within the distance range[i] of city i. (The distance between two cities is the smallest number of railroad segments one needs to travel in order to get from one city to the other. For example, if N=17 and range[2]=3, the cities directly reachable from city 2 are the cities {16,0,1,2,3,4,5}.)

You are also given ints startCity and endCity. Bob starts his tour in the city startCity and wants to end it in the city endCity. Calculate and return the minimum number of succesive direct trains he needs to take.

Constraints

  • range will contain N elements, where N is between 2 and 50, inclusive.
  • Each element of range will be between 1 and 50, inclusive.
  • startCity will be between 0 and N-1, inclusive.
  • endCity will be between 0 and N-1, inclusive.
  • startCity and endCity will be different.
Examples
0)
{2,1,1,1,1,1}
1
4
Returns: 2

Bob wants to get from city 1 to city 4. The optimal solution is to travel from city 1 to city 0, and then (as range[0]=2) from city 0 to city 4.

1)
{2,1,1,1,1,1}
4
1
Returns: 3

This is the same test case as Example 0, only startCity and endCity have been swapped. Note that the answer is now 3 instead of 2.

2)
{2,1,1,2,1,2,1,1}
2
6
Returns: 3

Bob starts in city 2. There are two optimal routes: (2->3->5->6) and (2->1->0->6).

3)
{3,2,1,1,3,1,2,2,1,1,2,2,2,2,3}
6
13
Returns: 4
4)
{2,4,2,3,4,1,4,2,5,4,3,3,5,4,5,2,2,4,4,3,3,4,2,3,5,4,2,4,1,3,2,3,4,1,1,4,4,3,5,3,2,1,4,1,4}
24
8
Returns: 5

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

Coding Area

Language: C++17 · define a public class TravelOnMars with a public method int minTimes(vector<int> range, int startCity, int endCity) · 121 test cases · 2 s / 256 MB per case

Submitting as anonymous