Arrival Lists
National Olympiad — National round (2010 season)
Submission name: order.cpp
Problem summary
Group arrival requests by vehicle: bus (b), train (t), own transport (o). Within each group, list requests in increasing arrival time. Print the groups in bus, train, own order and omit empty groups.
Source clarification. The PDF says N + 3 output lines but also explicitly omits empty group headings. The latter rule is followed, so the actual count is N plus the number of nonempty groups.
Input
N followed by N strings xhh:mm, where x is b, t, or o.
Output
For every nonempty group, its heading bus, train, or own, then its original request strings in time order.
Constraints
2 ≤ N ≤ 20; times use two-digit hours and minutes.
Worked example
An independently prepared example for this explanation.
Input
4 b12:24 o13:05 b11:25 t17:05
Output
bus b11:25 b12:24 train t17:05 own o13:05
Solution analysis
- Collect each request into one of three vectors according to its first character. The output group order is fixed independently of alphabetical order.
- Within a group all prefixes agree, and zero-padded hh:mm strings sort in chronological order. Sort each vector and print its heading only when it contains requests.
- In the sample the two bus requests become b11:25 and b12:24. Train comes next, followed by own transport, regardless of their arrival times relative to buses.
Why it works
The grouping step places every request in exactly its specified vehicle category. Lexicographic order within each group agrees with hour then minute order. Printing the nonempty groups in the required fixed order therefore satisfies both ordering rules and preserves all requests.
Watch out. Do not sort all requests by their prefix: alphabetical order would put own before train. Omit empty headings.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> groups[3];
for (int i = 0; i < n; i++) {
string request;
cin >> request;
int group = request[0] == 'b' ? 0 : (request[0] == 't' ? 1 : 2);
groups[group].push_back(request);
}
string headings[3] = {"bus", "train", "own"};
for (int group = 0; group < 3; group++) {
if (groups[group].empty()) {
continue;
}
// Zero-padded hh:mm strings have chronological lexical order.
sort(groups[group].begin(), groups[group].end());
cout << headings[group] << '\n';
for (const string &request : groups[group]) {
cout << request << '\n';
}
}
}