색 섞기 | cho.sh

문제

프랭크는 런던에 살고, 게임과 수학을 좋아한다. 요즘은 휴대폰으로 간단한 게임을 한다. 색이 있는 토큰이 한 줄로 놓여 있고, 한 차례마다 인접한 두 토큰을 합쳐서 정해진 색의 토큰 하나로 바꾼다. 줄에 토큰이 하나만 남을 때까지 이 과정을 반복한다.

아무 두 색이나 합칠 수 있는 것은 아니다. 합칠 수 있는 조합은 규칙으로 정해져 있다. 예를 들어 규칙이

Blue + Yellow → Green
Yellow + Red → Orange
Blue + Orange → Brown

이고 토큰이 (Blue, Yellow, Red) 순서로 놓여 있으면, 두 차례 만에 Brown 토큰을 만들어 게임을 끝낼 수 있다. (Blue, Yellow, Red) → (Blue, Orange) → (Brown)

규칙은 두 색의 순서를 가리지 않는다. 규칙 $s_1 + s_2 \to s_3$ 이 있으면 인접한 두 토큰이 $(s_1, s_2)$ 로 놓여 있어도 $(s_2, s_1)$ 로 놓여 있어도 $s_3$ 토큰 하나로 합칠 수 있다.

프랭크는 지금 발렌시아에서 열리는 프로그래밍 대회에 참가하는 중이고, 대학으로 가는 트램을 기다리며 이 게임으로 시간을 보내고 있다. 그런데 햇빛이 너무 강해서 화면이 잘 보이지 않는다. 각 토큰의 색은 어느 정도만 짐작할 수 있어서, 자기 짐작대로 가장 그럴듯한 진행을 따라갔을 때 마지막에 어떤 색이 남을지 알고 싶어졌다. 두 색 $A$ 와 $B$ 의 확신도를 알고 규칙 $A + B \to C$ 를 적용하면, 얻은 색 $C$ 의 확신도는 $\mathrm{cer}(C) = \mathrm{cer}(A) \times \mathrm{cer}(B)$ 이다.

한 번의 진행은 토큰마다 색 하나를 고르고 규칙에 맞게 줄 전체를 토큰 하나로 합치는 것이고, 그 진행의 확신도는 고른 색의 확신도를 모두 곱한 값이다.

입력

첫 줄에 합칠 수 있는 색 조합을 나타내는 규칙의 수 $R$ 이 주어진다. ( $0 < R \le 100$ )

다음 $R$ 개의 줄에 각각 세 문자열 $s_1$ , $s_2$ , $s_3$ 이 주어지고, 이는 규칙 $s_1 + s_2 \to s_3$ 을 뜻한다.

그 다음 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 토큰 줄의 길이 $C$ 가 주어진다. ( $0 < C \le 500$ )

이어지는 $C$ 개의 줄은 각각 토큰 하나를 나타낸다. 색 $k$ 와 그 색의 확신도 $\mathrm{cer}(k)$ 를 짝지어 차례로 나열하고 END로 끝난다. ( $0 < \mathrm{cer}(k) \le 1.0$ )

한 토큰의 확신도를 모두 더하면 항상 $1.0$ 이다. 테스트 케이스에 나오는 색은 모두 규칙에 먼저 나온 색이다.

출력

테스트 케이스마다 한 줄에 답을 출력한다.

토큰마다 색 하나를 골라 규칙에 맞게 줄 전체를 토큰 하나로 합칠 수 있으면, 고른 색의 확신도를 곱한 값이 가장 큰 진행에서 마지막에 남는 색을 출력한다. 가장 큰 확신도를 여러 색이 함께 얻으면 사전순(아스키 코드 순)으로 가장 앞서는 색을 출력한다.

$C = 1$ 이면 합칠 것이 없으므로 그 토큰에서 확신도가 가장 큰 색이 답이다.

게임을 끝내는 진행이 하나도 없으면 GAMEOVER를 출력한다.

힌트

첫 번째 예제의 첫 케이스에는 토큰이 두 개뿐이다. 두 번째 토큰이 Yellow인 것은 확실하지만 첫 번째 토큰은 Red일 수도 있고 Orange일 수도 있다. 게임을 끝내는 방법은 두 가지다.

(Red, Yellow) → (Orange), 확신도 $0.7$ . 규칙 Yellow + Red → Orange를 순서를 뒤집어 적용했다.
(Orange, Yellow) → (Yellow), 확신도 $0.3$ .

첫 번째가 더 그럴듯하므로 마지막 색은 Orange다.

두 번째 케이스에는 토큰과 짐작이 더 많다. 가능한 진행 두 가지를 보면

(Blue, Yellow, Yellow, Red) → (Blue, Yellow, Orange) → (Blue, Yellow) → (Green), 확신도 $0.006$
(Green, Red, White, Black) → (Green, Pink, Black) → (Green, Red) → (Yellow), 확신도 $0.036$

두 번째가 더 그럴듯하므로 답은 Yellow다.

세 번째 케이스에서는 토큰이 Blue와 Orange임이 확실하다. 이 두 색을 합치는 규칙이 없어서 게임을 끝낼 수 없다.

두 번째 예제의 첫 케이스는 확신도가 같은 결과가 둘 나오는 경우다. (Red, Red, Yellow)에서 앞의 두 토큰을 먼저 합치면 Red + Red → Blue, Blue + Yellow → Green이 되어 Green이 남고, 뒤의 두 토큰을 먼저 합치면 Red + Yellow → Purple, Red + Purple → Cyan이 되어 Cyan이 남는다. 두 진행의 확신도가 모두 $1.0$ 이므로 사전순으로 앞서는 Cyan을 출력한다.