Simultaneous Buses
National Olympiad — National round (2012 season)
Submission name: buses.cpp
Problem summary
Four bus routes depart together and then repeat every x,y,z,t minutes. Find the smallest positive elapsed time until all four depart together again.
Input
Four positive integer periods x, y, z, t.
Output
Elapsed whole hours and remaining minutes, separated by a space.
Constraints
1 ≤ x,y,z,t ≤ 10,000.
Worked example
An independently prepared example for this explanation.
Input
10 12 15 20
Output
1 0
Solution analysis
- The elapsed time must be a multiple of every route period. Compute their lcm by merging one period at a time with gcd.
- After finding total minutes, divide by 60 for hours and take remainder modulo 60 for minutes. The requested output is elapsed time, not the next clock reading.
- The lcm of 10,12,15,20 is 60 minutes, giving 1 0. For 2,3,5,6 it is 30 minutes, giving 0 30.
Why it works
The iterative gcd–lcm formula produces the least positive common multiple of the four periods. Exactly at these common multiples all routes depart, so the least one is the next simultaneous departure. Quotient and remainder convert it without changing the duration.
Watch out. Do not add the initial 07:00 time. The lcm can exceed 32-bit range; use long long.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <numeric>
using namespace std;
int main() {
long long minutes = 1;
for (int i = 0; i < 4; i++) {
long long period;
cin >> period;
// The next common departure is the lcm of all route periods.
minutes = minutes / gcd(minutes, period) * period;
}
cout << minutes / 60 << ' ' << minutes % 60 << '\n';
}