Green Light

Photo by wgelissen.

Sarah is cycling to work. On her way there, she encounters the same traffic light every day. Before she reaches the lights, she alternates between using social media on her mobile device and glancing at the traffic lights, observing if they are green, yellow or red at that time. From experience, she knows that the lights have a fixed green-yellow-red cycle, and how long each stage lasts. So if the light goes from red to green at time $T$, she knows it will stay green until (but not including) $T+T_ g$, then go yellow until (but not including) $T+T_ g+T_ y$ and finally stay red until (but not including) $T+T_ g+T_ y+T_ r$, at which point it will turn green again. However, she does not know $T$, the time at which the traffic light cycle starts. Based on her observations, she can deduce what values of $T$ are (im)possible. Assuming that all possible values of $T$ that are consistent with her observations are equally likely, can you compute the probability that the lights will be green at a certain time?


  • The first line contains three positive integers $T_ g$ $T_ y$ $T_ r$, corresponding to the duration (in seconds) for which the lights stay green, yellow, and red ($0 < T_ g,T_ y,T_ r \leq 10^8$).

  • The second line contains a single positive integer $n$, the number of times Sarah looked at the lights ($3 \leq n < 1\, 000$).

  • Each of the next $n$ lines contains one integer $0\leq t \leq 10^9$ followed by a color $c$: the time (in seconds) of the observation and color of the lights at that moment. The times of the observations are given in strictly increasing order. Sarah did see the lights being each color (green, yellow, and red) at least once.

  • The last line contains an integer $ 0 \leq t_ q \leq 10^9$ and a color $c_ q$. These specify the question asked: What is the probability of the lights being color $c_ q$ at time $t_ q$?


  • $0 \leq p \leq 1$, the probability of the lights being color $c_ q$ at time $t_ q$. Your answer is considered correct if it has absolute or relative error of at most $10^{-3}$.

Sample Input 1 Sample Output 1
4 4 4
2 green
18 yellow
34 red
5 green
Sample Input 2 Sample Output 2
4 4 4
2 green
6 yellow
10 red
14 green
4 red
Sample Input 3 Sample Output 3
6 6 6
5 green
6 green
9 yellow
12 yellow
15 red
19 red
7 green
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 7.4hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in