Задача D. Камень, ножницы, бумага и другие ≡

Условие

Глеб и Вася, студенты Института математики и компьютерных наук ДВФУ, часто играют в игру "камень, ножницы, бумага", чтобы определить, кто пойдёт мыть тряпку для стирания с доски.

Правила этой игры таковы: участники произносят фразу "камень, ножницы, бумага раз, два, три", после чего каждый участник показывает рукой один из трёх предметов: камень, ножницы или бумагу. В игре считается, что камень ломает ножницы, ножницы режут бумагу, бумага накрывает камень. Если, например, Глеб выбрал бумагу, а Вася выбрал ножницы, то Вася побеждает, а если оба игрока выбрали камень, то объявляется ничья.

Однажды Глеб и Вася захотели обобщить игру "камень, ножницы, бумага". Теперь в игре задействовано N предметов. Задаётся список пар предметов. Считается, что если один игрок выбрал первый предмет из некоторой пары, а другой игрок — второй предмет из этой пары, то тот, кто выбрал первый предмет из пары, побеждает. Если игроки выбрали пару предметов, которая не встречается в списке пар, то объявляется ничья.

Напишите программу, принимающую на вход список предметов, список пар предметов и список игр и выводящую результаты игр.

Рекомендуется рассмотреть частичные решения

1 ≤ M, K ≤ 200

Формат входного файла

Первая строка входного файла содержит целое число N — количество предметов. Далее следуют N строк — названия предметов. Длина названия составляет от 1 до 20 символов. Названия состоят из маленьких латинских букв. Все названия различны.

Следующая строка содержит целое число M — длину списка пар предметов. Далее следуют 2 × M строк — пары предметов. В каждой из этих строк может содержаться только название предмета из списка предметов. Никакие два предмета не могут содержаться одновременно в двух парах.

Следующая строка содержит целое число K — количество игр. Далее следуют 2 × K строк. В каждой из этих строк может содержаться только название предмета из списка предметов.

Формат выходного файла

Выходной файл должен содержать K чисел. Для каждой игры должно быть выведено число 1, если выиграл первый игрок, число 2, если выиграл второй игрок, и число 0, если игроки сыграли вничью.

Ограничения

2 ≤ N ≤ 1000

1 ≤ M, K ≤ 20000

Примеры тестов

3
kamen
nozhnitsy
bumaga
3
kamen
nozhnitsy
nozhnitsy
bumaga
bumaga
kamen
2
bumaga
nozhnitsy
kamen
kamen

2 0

Разбор

Во-первых, считаем список названий. Поскольку все названия уникальны, каждое из них можно после чтения заменить его номером.

Чтобы запомнить пары названий. используем двумерный логический массив (матрицу смежности), в которой элемент a_i,j будет истинным, если i-й предмет побеждает j-й.

Теперь для каждой игры, в которой первый игрок назвал предмет с номером i, а второй — с номером j, мы можем определить:

• если a_i,j истинно, победил первый игрок,
• если a_j,i истинно, победил второй игрок,
• иначе ничья

В случае, если для определения номера по названию предмета используется простой цикл, общая сложность алгоритма будет составлять O((M + K) × L × N), где L — максимальная длина названия.

Для эффективного решения можно либо заранее отсортировать названия в алфавитном порядке и использовать двоичный поиск, либо применить эффективную структуру данных типа сбалансированного дерева или хеш-таблицы. В зависимости от реализации, алгоритмическая сложность будет O((M + K) × L × log N) или меньше, что достаточно для прохождения всех тестов.

Чтобы не выписывать алгоритмы поиска и сортировки, можно воспользоваться стандартной библиотекой языка программирования: в языке C++ классом map, в языке Паскаль — классом TStringList.

Иллюстрация к тесту 6