Last Show at the Zoo
National Olympiad — National round (2009 season)
Submission name: zoo.cpp
Problem summary
Several shows take place during one day. Given each start hour, start minute, and duration in minutes, find the latest finishing time.
Input
N, then N lines of hour, minute, duration.
Output
The finishing hour and minute of the last show, separated by a space.
Constraints
2 ≤ N ≤ 10; shows take place within one day. Further numeric bounds are not stated.
Worked example
An independently prepared example for this explanation.
Input
4 12 15 120 13 20 25 11 25 230 14 10 45
Output
15 15
Solution analysis
- Convert each start time to minutes from the beginning of the day: 60 × hour + minute. Adding the duration gives its finishing time in the same unit.
- Keep the greatest finish seen. Only convert this maximum back to hours and minutes, using division and remainder by 60.
- The sample finishes are 14:15, 13:45, 15:15, and 14:55. The largest is 15:15, even though that show does not start latest.
Why it works
Each computed finish equals the show’s start plus its duration. Maintaining the maximum therefore gives the latest finish among all processed shows, and after all N shows it gives the required answer. Division and remainder reconstruct its hour and minute.
Watch out. Compare finishing times, not starting times. Minutes may carry into a later hour.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
long long latest = 0;
for (int i = 0; i < n; i++) {
long long hour, minute, duration;
cin >> hour >> minute >> duration;
// Compare finish times measured in minutes from midnight.
latest = max(latest, 60 * hour + minute + duration);
}
cout << latest / 60 << ' ' << latest % 60 << '\n';
}