Meeting at the Lift
National Olympiad — National round (2013 season)
Submission name: meeting.cpp
Problem summary
Students travel from home to a lift. Cabins depart every 20 minutes from 07:00 and take 20 minutes to reach the top. A student arriving exactly at departure must take the next cabin. Find when everyone has arrived at the top and list all last arrivals.
Input
N; then N lines hh:mm tt, giving home departure time and travel minutes to the lower station. Students are numbered from 1 in input order.
Output
Meeting time hh:mm; then indices of last arrivals, in input order, at most 10 per line, comma-separated with no final comma.
Constraints
5 ≤ N ≤ 40; 05 ≤ hh ≤ 15; 0 ≤ mm ≤ 59; 0 < tt ≤ 180; everyone reaches the lift before its 19:00 closing.
Worked example
An independently prepared example for this explanation.
Input
5 07:00 25 08:45 30 08:00 38 07:30 47 08:30 22
Output
09:40 2
Solution analysis
- Convert home departure to minutes and add tt. If arrival is before 07:00, choose the 07:00 cabin; otherwise choose the first 20-minute departure strictly after arrival.
- Add 20 minutes for the ride. The maximum top-arrival time is the meeting time. Keep all student indices attaining that maximum.
- Student 2 reaches the lower station at 09:15, boards at 09:20, and reaches the top at 09:40. All others arrive earlier in the first sample.
Why it works
The rounding formula selects the earliest permissible cabin for each student, including the strict departure rule and opening time. Adding the ride gives each earliest top arrival. Everyone is present exactly when the latest arrival occurs, and indices matching this maximum are precisely the last students.
Watch out. A student at 07:00 boards at 07:20. Format time with leading zeroes and wrap indices after every 10 without a trailing comma.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int n;
cin >> n;
int latest = -1;
vector<int> last;
for (int i = 1; i <= n; i++) {
int hour, minute, travel;
char colon;
cin >> hour >> colon >> minute >> travel;
int arrival = hour * 60 + minute + travel;
int cabin = 420;
if (arrival >= 420) {
// The +1 enforces boarding strictly after arrival.
cabin = 420 + ((arrival - 420) / 20 + 1) * 20;
}
int top = cabin + 20;
if (top > latest) {
latest = top;
last.clear();
}
if (top == latest) {
last.push_back(i);
}
}
cout << setfill('0') << setw(2) << latest / 60 << ':' << setw(2) << latest % 60 << '\n';
for (int i = 0; i < static_cast<int>(last.size()); i++) {
if (i % 10 != 0) {
cout << ',';
}
cout << last[i];
if (i % 10 == 9 || i + 1 == static_cast<int>(last.size())) {
cout << '\n';
}
}
}