초록불

시간 제한1초메모리 제한512 MB

요약
고정된 신호등 단계 길이와 관측 색상이 주어질 때, 알 수 없는 사이클 시작 시각에서 tq에 cq가 켜질 확률을 구합니다.
난이도

보통10점 중 7점

유형
수학, 구간, 완전 탐색, 정수론
정답자
아직 제출이 없습니다

문제

Sarah는 자전거를 타고 출근한다. 가는 길에 그녀는 매일 같은 신호등을 만난다. 신호등에 도착하기 전, 그녀는 휴대폰으로 소셜 미디어를 사용하는 것과 신호등을 힐끗 보는 것을 번갈아 하며 그 순간 신호등이 초록, 노랑, 빨강 중 어느 색인지 관찰한다. 경험을 통해 그녀는 신호등이 고정된 초록-노랑-빨강 주기를 가지며 각 단계가 얼마나 지속되는지 안다. 따라서 신호등이 시각 T에 빨강에서 초록으로 바뀐다면, T + Tg까지(그 시각은 포함하지 않음) 초록으로 유지되고, 그다음 T + Tg + Ty까지(포함하지 않음) 노랑으로, 마지막으로 T + Tg + Ty + Tr까지(포함하지 않음) 빨강으로 유지되며, 그 시각에 다시 초록으로 바뀐다는 것을 그녀는 안다. 그러나 그녀는 신호등 주기가 시작되는 시각인 T를 모른다. 관찰을 바탕으로 그녀는 어떤 T 값이 가능하고 불가능한지 추론할 수 있다. 그녀의 관찰과 일치하는 각각의 가능한 T 값이 모두 같은 확률을 가진다고 가정할 때, 특정 시각에 신호등이 초록일 확률을 구할 수 있는가?

입력

  • 첫째 줄에는 세 개의 양의 정수 Tg, Ty, Tr이 주어진다. 이는 신호등이 각각 초록, 노랑, 빨강으로 유지되는 시간(초)이다(0 < Tg, Ty, Tr ≤ 108).
  • 둘째 줄에는 양의 정수 n이 주어진다. 이는 Sarah가 신호등을 본 횟수이다(3 ≤ n < 1000).
  • 다음 n개의 줄 각각에는 정수 0 ≤ t ≤ 109와 색상 c가 주어진다. 이는 관찰 시각(초)과 그 순간 신호등의 색상이다. Sarah는 각 색상(초록, 노랑, 빨강)을 적어도 한 번씩 보았다.
  • 마지막 줄에는 정수 0 ≤ tq ≤ 109와 색상 cq가 주어진다. 이는 질문을 나타낸다. 시각 tq에 신호등이 색상 cq일 확률은 얼마인가?

출력

  • 시각 tq에 신호등이 색상 cq일 확률 0 ≤ p ≤ 1을 출력한다. 정답과의 차이가 절댓값 또는 상댓값으로 10−3 이하이면 정답으로 인정된다.

예제3

  1. 예제 1

    입력
    4 4 4
3
2 green
18 yellow
34 red
5 green
    예상 출력
    0.25

  2. 예제 2

    입력
    4 4 4
4
2 green
6 yellow
10 red
14 green
4 red
    예상 출력
    0

  3. 예제 3

    입력
    6 6 6
6
5 green
6 green
9 yellow
12 yellow
15 red
19 red
7 green
    예상 출력
    1