The Journey Home
National Olympiad — National round (2014 season)
Submission name: wayback.cpp
Problem summary
Choose up to three earliest departures whose route contains the desired city and whose station can be reached at least five minutes before departure. Travel times to the train and bus stations may differ. The timetable is already sorted by departure time, and all times are in one day.
Source clarification. The PDF lists nonzero bounds for minutes even though hh:mm convention includes 00. The solution accepts the full ordinary minute range 00–59.
Input
Finish time hh:mm and destination; then train-station travel time T1, bus-station travel time T2 and N. Each departure gives hh:mm, t or b, and up to five city names terminated by EOR.
Output
Print up to three qualifying departures as train hh:mm or bus hh:mm. If none qualify print No direct connection!
Constraints
1 ≤ N ≤ 24; travel times ≤ 59 minutes; times within one day; city names have at most 20 uppercase letters or underscores.
Worked example
An independently prepared example for this explanation.
Input
12:35 JAMBOL 45 55 7 12:44 t SHUMEN KASPICHAN RAZGRAD RUSE EOR 12:55 b SHUMEN RAZGRAD RUSE EOR 13:45 t TULOVO JAMBOL SLIVEN PLOVDIV EOR 14:05 b VTARNOVO PLEVEN SOFIA EOR 14:10 b JAMBOL PLOVDIV HASKOVO EOR 15:20 b SHUMEN PLEVEN SOFIA EOR 16:47 t VARNA GORNA_ORJAHOVIZA VTARNOVO SOFIA EOR
Output
train 13:45 bus 14:10
Solution analysis
- Convert each hh:mm string to 60 × hours + minutes. A departure is reachable exactly when its time is at least finish + travel time + 5.
- Read every route through EOR and record whether it contains the destination. A reachable departure without that city is still unsuitable. Because departures are already sorted, retain only the first three suitable ones.
- In the example the team finishes at 12:35. A train must depart at 13:25 or later and a bus at 13:35 or later. The 13:45 train and 14:10 bus both visit JAMBOL, producing the two output lines.
Why it works
The time test is equivalent to arrival at least five minutes before departure, and the route test is equivalent to visiting the destination. Thus exactly suitable departures pass. Reading the sorted timetable and accepting its first three matches yields the earliest available options.
Watch out. Equality at the five-minute boundary is allowed. Keep reading all route tokens even after a match. Do not wrap departures into the next day.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int minutes(const string &time) {
return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string finish, destination;
cin >> finish >> destination;
int trainTravel, busTravel, n;
cin >> trainTravel >> busTravel >> n;
int found = 0;
for (int i = 0; i < n; ++i) {
string departure, city;
char kind;
cin >> departure >> kind;
bool visits = false;
while (cin >> city && city != "EOR") {
if (city == destination) {
visits = true;
}
}
// Arrival exactly five minutes before departure is still early enough.
int travel = kind == 't' ? trainTravel : busTravel;
if (visits && minutes(departure) >= minutes(finish) + travel + 5 && found < 3) {
cout << (kind == 't' ? "train " : "bus ") << departure << '\n';
++found;
}
}
if (found == 0) {
cout << "No direct connection!\n";
}
return 0;
}