Under construction

Still being built. Things may change

Green Light

Time limit1sMemory limit512 MB

Summary
Given color observations and fixed traffic-light phase lengths, find the probability that the unknown cycle offset gives color cq at time tq.
Level

Medium7 of 10

Topics
Math, Intervals, Brute force, Number theory
Solved
No attempts yet

Problem

Sarah is cycling to work. On her way there, she encounters the same traffic light every day. Before she reaches the light, she alternates between using social media on her mobile device and glancing at the traffic light, observing whether it is green, yellow, or red at that moment. From experience, she knows that the light has 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 + Tg, then go yellow until (but not including) T + Tg + Ty, and finally stay red until (but not including) T + Tg + Ty + Tr, 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 which values of T are possible and which are impossible. Assuming that each possible value of T consistent with her observations is equally likely, can you compute the probability that the light will be green at a certain time?

Input

  • The first line contains three positive integers Tg, Ty, Tr, the durations (in seconds) for which the light stays green, yellow, and red (0 < Tg, Ty, Tr ≤ 108).
  • The second line contains a single positive integer n, the number of times Sarah looked at the light (3 ≤ n < 1000).
  • Each of the next n lines contains one integer 0 ≤ t ≤ 109 followed by a color c: the time (in seconds) of the observation and the color of the light at that moment. Sarah did see the light being each color (green, yellow, and red) at least once.
  • The last line contains an integer 0 ≤ tq ≤ 109 and a color cq. These specify the question asked: what is the probability of the light being color cq at time tq?

Output

  • Output 0 ≤ p ≤ 1, the probability of the light being color cq at time tq. Your answer is correct when it differs from the actual answer by at most 10−3, either absolutely or relatively.

Examples3

  1. Example 1

    Input
    4 4 4
3
2 green
18 yellow
34 red
5 green
    Expected output
    0.25

  2. Example 2

    Input
    4 4 4
4
2 green
6 yellow
10 red
14 green
4 red
    Expected output
    0

  3. Example 3

    Input
    6 6 6
6
5 green
6 green
9 yellow
12 yellow
15 red
19 red
7 green
    Expected output
    1