Journey Through Traffic Lights
National Olympiad — Regional round (2021 season)
Submission name: lights.cpp
Problem summary
A truck travels from position 0 to L at one distance unit per second. Each light starts a repeating red-for-R, green-for-G cycle at time 0. At a red light the truck waits until green; at a green light it passes immediately. Find its arrival time.
Source clarification. The statement promises increasing positions, but official sample 2 lists 7, 14, 15, 5. Sorting those rows gives its published answer 36 and also works for all inputs satisfying the prose.
Input
N L, followed by N rows D R G describing distinct light positions and durations.
Output
The arrival time at position L in seconds.
Constraints
1 ≤ N ≤ 100; 1 ≤ D < L ≤ 1000; 1 ≤ R,G ≤ 100. The prose says increasing D; sorting also handles the unsorted second official sample.
Worked example
An independently prepared example for this explanation.
Input
2 10 3 5 5 5 2 2
Output
12
Solution analysis
- Sort lights by their distance from the start, then keep the current position and elapsed time. Add the distance to the next light before checking its colour.
- For a light with period R+G, the phase is time mod (R+G). Phases below R are red, so wait R−phase seconds; phase exactly R is already green.
- In the sample, the truck reaches position 3 at time 3 and waits until time 5. It reaches position 5 at time 7, which is green for that light. The remaining five distance units give arrival at time 12.
Why it works
At every processed light, elapsed time equals the actual earliest passage time there. Travel to the next light takes its distance difference; the modular phase determines exactly the wait required by its cycle. The same invariant then holds at the next light. Adding the final distance gives the journey time.
Watch out. Use strict phase < R: the instant red ends is green. Cycles use absolute elapsed time, including earlier waits.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Light {
int position;
int red;
int green;
};
int main() {
int n, length;
cin >> n >> length;
vector<Light> lights(n);
for (Light& light : lights) {
cin >> light.position >> light.red >> light.green;
}
sort(lights.begin(), lights.end(), [](const Light& a, const Light& b) {
return a.position < b.position;
});
int position = 0;
int elapsed = 0;
for (const Light& light : lights) {
elapsed += light.position - position;
// Use absolute time: previous waits also advance this light.
int phase = elapsed % (light.red + light.green);
if (phase < light.red) {
elapsed += light.red - phase;
}
position = light.position;
}
elapsed += length - position;
cout << elapsed << '\n';
}