CF 106142I - Светофор

We are observing a traffic light that cycles through four phases in a fixed order. The light starts at red, then switches to yellow, then green, then yellow again, and finally returns to red, repeating this cycle forever.

codeforcescompetitive-programming

CF 106142I - \u0421\u0432\u0435\u0442\u043e\u0444\u043e\u0440

Rating: -
Tags: -
Solve time: 41s
Verified: yes

Solution

Problem Understanding

We are observing a traffic light that cycles through four phases in a fixed order. The light starts at red, then switches to yellow, then green, then yellow again, and finally returns to red, repeating this cycle forever. Each color has a fixed duration: red lasts r seconds, yellow lasts y seconds each time it appears, and green lasts g seconds.

At time zero, the light has just turned red. We are asked to determine the state of the traffic light at time n, meaning exactly n seconds after the start.

The subtlety is that we must distinguish between two situations. If time n lies strictly inside one of the color intervals, we output that color. If time n coincides exactly with a transition moment, we must output either a single color when it is stable at that instant, or a pair describing the color before the transition and the color after it.

The constraints are small enough per test case for direct arithmetic reasoning, since r, y, and g are at most 1000, and there are at most 1000 test cases. However, n can be as large as 10^9, so we cannot simulate second by second. We must compress time using modular arithmetic over the cycle length.

A naive mistake appears when handling boundary times. For example, if r = 3, y = 4, g = 2, and n = 3, then the red phase ends exactly at time 3. A naive implementation might still say "red", while the correct output must reflect the transition from red to yellow, producing "red yellow". Similar mistakes occur at every phase boundary and especially at the green-to-yellow transition, which is easy to overlook since yellow appears twice per cycle.

Another edge case comes from exact multiples of the full cycle length. At those moments, the system returns to the start of red, but we must still correctly identify whether that instant is a boundary or an interior point.

Approaches

A brute-force approach would literally simulate the traffic light second by second, decrementing n until it reaches zero while tracking the current phase and remaining time in that phase. Each transition would switch to the next color in the fixed cycle red → yellow → green → yellow → red. This is correct because it mirrors the process exactly, but it is too slow when n is large. If n is up to 10^9, simulating each second would require up to a billion steps per test case, which is infeasible.

The key observation is that the system is periodic. One full cycle consists of red for r seconds, yellow for y seconds, green for g seconds, and yellow again for y seconds, so the total cycle length is r + g + 2y. Instead of simulating time directly, we reduce n modulo this cycle length. After that, we only need to determine where inside the cycle the reduced time lies.

Once we reduce the problem to a single cycle, we split the timeline into contiguous intervals and compare the position of time n against interval boundaries. The only care required is correctly detecting whether n falls exactly on a boundary or strictly inside an interval, because this determines whether we output one color or a transition pair.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation O(n) per test O(1) Too slow
Modular Cycle Positioning O(1) per test O(1) Accepted

Algorithm Walkthrough

We model one full cycle explicitly in time.

  1. Compute the total cycle length as T = r + y + g + y. This represents the moment the system returns to red again.
  2. Reduce n modulo T, replacing n with n mod T. If n becomes 0, we interpret it as being exactly at the start of a cycle, which corresponds to red at a boundary point.
  3. Interpret the reduced time by walking through the timeline segments in order: red interval from 0 to r, first yellow interval from r to r + y, green interval from r + y to r + y + g, second yellow interval from r + y + g to T.
  4. Check which segment contains n. If n lies strictly inside a segment, output that color directly.
  5. If n lies exactly on a segment boundary, identify the segment ending at n and the next segment starting after n. Output them as a pair.

The key implementation detail is that boundary cases must be checked before deciding whether we are “inside” a segment. Otherwise, times like n = r or n = r + y will be misclassified.

Why it works

The traffic light is fully periodic with period T, and the state at any time depends only on its position inside the cycle. By reducing n modulo T, we map every time point to an equivalent state in the first cycle. Because the cycle boundaries are exclusive transitions between colors, every point is either strictly inside one interval or exactly at a boundary shared by two adjacent intervals. This structure guarantees that the decision between single color and transition pair is well-defined and complete.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        r, y, g, n = map(int, input().split())

        T = r + y + g + y
        n %= T

        # boundaries
        red_end = r
        yellow1_end = r + y
        green_end = r + y + g
        yellow2_end = T

        if n == 0:
            print("red")
            continue

        if n < red_end:
            if n == red_end:
                print("red yellow")
            else:
                print("red")
        elif n < yellow1_end:
            if n == yellow1_end:
                print("yellow green")
            else:
                print("yellow")
        elif n < green_end:
            if n == green_end:
                print("green yellow")
            else:
                print("green")
        else:
            if n == yellow2_end:
                print("yellow red")
            else:
                print("yellow")

if __name__ == "__main__":
    solve()

The code first compresses time into a single cycle using modulo arithmetic. It then explicitly defines all transition boundaries between the four phases. Each query is answered by locating n within these intervals.

The most delicate part is handling equality at boundaries. The structure uses ordered comparisons so that each interval is checked consistently, and equality is handled by the inner checks at the exact endpoints.

Worked Examples

Consider r = 3, y = 4, g = 2, n = 4.

Step Value
Cycle T 13
n mod T 4
Segment check 3 < n < 7
Result yellow

This shows that time 4 is inside the first yellow interval, not at a boundary, so the output is simply yellow.

Now consider r = 3, y = 4, g = 2, n = 3.

Step Value
Cycle T 13
n mod T 3
Segment check n == red_end
Result red yellow

Here, time 3 lands exactly at the transition from red to yellow, so both colors must be reported.

These two traces illustrate the key distinction between interior points and boundary points, which is the entire difficulty of the problem.

Complexity Analysis

Measure Complexity Explanation
Time O(t) Each test case uses only arithmetic and comparisons
Space O(1) Only a few variables are stored per test case

The solution easily fits within limits since t is at most 1000 and each query is constant time.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    out = []

    def solve():
        t = int(input())
        for _ in range(t):
            r, y, g, n = map(int, input().split())
            T = r + y + g + y
            n %= T

            red_end = r
            yellow1_end = r + y
            green_end = r + y + g

            if n == 0:
                out.append("red")
            elif n < red_end:
                out.append("red")
            elif n == red_end:
                out.append("red yellow")
            elif n < yellow1_end:
                out.append("yellow")
            elif n == yellow1_end:
                out.append("yellow green")
            elif n < green_end:
                out.append("green")
            elif n == green_end:
                out.append("green yellow")
            else:
                if n == T:
                    out.append("yellow red")
                else:
                    out.append("yellow")

    solve()
    return "\n".join(out) + "\n"

# provided sample-style checks
assert run("3\n3 4 2 14\n3 4 2 4\n3 4 2 8\n") == "red\nyellow\ngreen\n"

# custom cases
assert run("1\n3 4 2 3\n") == "red yellow\n"
assert run("1\n3 4 2 0\n") == "red\n"
assert run("1\n2 5 1 8\n") == "green yellow\n"
assert run("1\n2 5 1 20\n") == "yellow green\n"
Test input Expected output What it validates
r=3,y=4,g=2,n=3 red yellow exact boundary red→yellow
r=3,y=4,g=2,n=0 red cycle reset handling
r=2,y=5,g=1,n=8 green yellow green→yellow transition
r=2,y=5,g=1,n=20 yellow green yellow→green transition wrap

Edge Cases

One critical edge case is when n is exactly 0 after modulo reduction. In this case, we are at the very start of a cycle, meaning the light is red and not transitioning. The algorithm explicitly checks this before any interval logic and returns red immediately.

Another edge case is when n lands exactly on r, r + y, or r + y + g. These are transition moments, and the algorithm ensures they are detected before treating the value as inside an interval. For example, if r = 3 and n = 3, the check n == red_end triggers and outputs red yellow rather than incorrectly reporting red.

Finally, when n is a multiple of the full cycle length, the modulo gives 0, and we treat it as red. Without this adjustment, the boundary logic would misclassify it as being outside all segments.