TopPilot
TCI '02 Semifinals 4 · 2002-11-22 · by chogyonim
Problem Statement
TopPilot airlines is committed to customer service and convenience. Thus, it is not simply enough to have a flight from San Francisco, CA to Hartford, CT. There must be a direct flight.
You will be given a
Write a method that, given these one-way flight paths, adds direct one-way flights between airports that are currently connected by non-direct one-way flights. For example, if there is a direct flight from SFO to JFK and a direct flight from JFK to LAX, and not a direct flight from SFO to LAX, then add a direct flight from SFO to LAX. Do not, however, add a direct flight from an airport to itself, even if a loop exists. Once this is done, the method should return the total number of flights provided by TopPilot airlines.
Notes
- If the destination airport does not appear as an element in destinations (which is always the case when it is greater than 19), there are no departing flights from that airport.
- Leading zeroes in the numbers are allowed.
Constraints
- No airport will have a direct flight to itself.
- destinations will have between 1 and 20 elements, inclusive.
- each element of destinations will contain only the characters '0' through '9', and commas ','.
- each element of destinations will be a comma delimited list of integers, with no numbers repeated, and no leading, trailing, or extra commas.
- each element of destinations will be contain between 1 and 50 characters, inclusive.
- destination airport numbers will be between 0 and 50, inclusive.
{"1","2","3"}
Returns: 6
There is a flight from airport 0 to airport 1, from 1 to 2, and from 2 to 3. We add a direct flight from 0 to 2, from 1 to 3, and from 0 to 3 (note that 3 is not an element, so it has no departing flights).
{"1","02","3","4,5"}
Returns: 14
We add flights from 0 to 2, 3, 4, and 5. We add flights from 1 to 3, 4, and 5. We add flights from 2 to 4 and 5. Together with the 5 flights we already have, there are 14 total.
{"1,2","0,2","1"}
Returns: 6
The only added flight is from 2 to 0.
{"1,5,7,8,13,15,16,23,26,35,32,41"
,"0,2,5,6,7,15,18,21,25,31,34,41,49,50"
,"5,10,15,20,25,30,35,40,45,50"}
Returns: 62
{"40,6,38,5,12","20,29,6,50,5,14,0","22,39,14,13,9,31,26,49,1,23","19,30,29,37,36,46,24,0","42,49","43,19,48,2,13,33,0","43,20,8,48","1","14,34","21,44,19,17,15,14,33,31,7,5,27,50,48,1,23","20,41,16,15,38,14,36,35,32,8,31,29,27,24","32,49,5,26,13,24,35,34","22,44,20,17,40,38,35,11,10,32,30,29,5,50,47,23","15,14,37,12,11,32,49,48,0","34","21,16,14,33","41,39,15,14,37,12,11,10,32,8,6,27,3,24,1","21,20,41,40,15,33,9,7,4,27,26,48,46","22,15,38,10,9,6,4,27,23","21,42,10,9,7,6,50,2,47"}
Returns: 748
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TopPilot with a public method int addFlights(vector<string> destinations) · 30 test cases · 2 s / 256 MB per case