CircularLine
SRM 399 · 2008-04-24 · by andrewzta
Problem Statement
There's a circular subway line that contains n stations numbered 0 through n-1. The time to travel between stations 0 and 1 is t[0], the time to travel between stations 1 and 2 is t[1], ..., the time to travel between stations n-1 and 0 is t[n-1]. You can travel between stations in either direction, so there are always two ways to get from one station to another without visiting the same station more than once. For example, if there are 4 stations, the two ways of getting from station 1 to station 3 are 1-2-3 and 1-0-3. The total travel time in the first case is t[1] + t[2], and in the second case, it is t[0] + t[3]. When a person needs to get from one station to another, she always chooses the faster of the two ways.
You are given a
Constraints
- t will contain between 3 and 50 elements, inclusive.
- Each element of t will be between 1 and 1000, inclusive.
{1,1,1,1}
Returns: 2
{1,4,4,1,5}
Returns: 7
The longest travel time is between stations 1 and 3.
{1,1,1000}
Returns: 2
You must never travel from station 2 to station 0 using the 1000 segment.
{1,1000,1,1000}
Returns: 1001
{1,1,1,1,4}
Returns: 4
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CircularLine with a public method int longestTravel(vector<int> t) · 70 test cases · 2 s / 256 MB per case