Змішування кольорів#7216

Змішування кольорів

10 секунд

64 мегабайти

Дуже складна

Френк живе в Лондоні й дуже захоплюється іграми та математикою. Нещодавно він почав грати в гру на своєму мобільному телефоні. Гра досить проста: є послідовність кольорових фігурок, і на кожному ході гравець повинен об'єднати пару сусідніх фігурок, щоб отримати нову фігурку певного кольору. Цей процес повторюється, поки вся послідовність не зведеться до однієї кінцевої фігурки. Проблема в тому, що не всі пари кольорів можуть об'єднуватися. Існує набір правил, що описують дозволені комбінації. Наприклад, розглянемо такі правила:

blue + yellow → green

yellow + red → orange

blue + orange → brown

і послідовність (blue, yellow, red). Гра може завершитися коричневою фігуркою за два кроки: (blue, yellow, red) → (blue, orange) → (brown).

Зараз Френк перебуває у Валенсії на відомому конкурсі з програмування, чекаючи трамвая, щоб дістатися до університету. Тим часом, він грає в цю гру, щоб скоротати час. Сонце світить так яскраво, що він не може чітко бачити екран свого телефону. Френк має певну впевненість щодо можливого кольору кожної фігурки і хоче дізнатися, яким буде кінцевий колір після найбільш ймовірного сценарію гри, оцінюючи вхідну послідовність.

Френк оцінює ймовірність отримання кольору C з комбінації кольорів A і B за правилом A + B → C як $cer (C) = cer (A) \cdot cer (B)$ cer(C) = cer(A) \cdot cer(B).

Вхідні дані

Перший рядок містить кількість правил $r$ ( $0 < r \leq 100$ 0 < r \le 100), що визначають можливі комбінації кольорів. Кожен з наступних $r$ рядків містить три рядки $s_{1}$ s_1, $s_{2}$ s_2, $s_{3}$ s_3, що описують комбінацію $s_{1} + s_{2} \to s_{3}$ s_1 + s_2 \to s_3. Наступний рядок задає кількість тестів $t$ . Для кожного тесту задається довжина $c$ ( $0 < c \leq 500$ 0 < c \le 500) вхідної послідовності фігурок. Кожен з наступних $c$ рядків описує фігурку, містячи список пар ( $k$ , $cer (k)$ ), що задають колір $k$ і відповідну ймовірність ( $0 < cer (k) \leq 1.0$ 0 < cer(k) \le 1.0). Список завершується словом END. Сума ймовірностей для кожної фігурки завжди дорівнює $1.0$ . Кожен колір у тестах спочатку зустрічається в правилах, що описують гру.

Вихідні дані

Для кожного тесту виведіть колір, з яким найбільш ймовірно закінчити гру. Якщо завершити гру неможливо, виведіть GAMEOVER.

Пояснення до прикладів

Перший тест

У першому тесті всього дві фігурки. Френк впевнений, що друга фігурка Yellow, але першою може бути Red або Orange. Є два можливих рішення гри:

1. (Red; Yellow) → (Orange) :

$cer (O r an g e) = 0.7$ cer(Orange) = 0.7

2. (Orange; Yellow) → (Yellow) :

$cer (Y e l l o w) = 0.3$ cer(Yellow) = 0.3

За оцінками Френка більш ймовірно закінчення $1$ , тому фінальний колір Orange.

Другий тест

У другому тесті є кілька фігурок і оцінок. Два можливих рішення:

1. (Blue,Yellow,Yellow,Red) → (Blue,Yellow,Orange) → (Blue,Yellow) → (Green)

$cer (G r ee n) = 0.006$ cer(Green) = 0.006

2. (Green,Red,White,Black) → (Green,Pink,Black) → (Green,Red) → (Yellow)

$cer (Y e l l o w) = 0.036$ cer(Yellow) = 0.036

За оцінками Френка більш ймовірно закінчення $2$ , тому фінальний колір Yellow.

Третій тест

Френк впевнений, що у нього є дві фігурки Blue і Orange. Не існує правила, за яким їх можна скомбінувати, тому гра не має рішення.

Приклади

Приклад 1