Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Игра в слова

(Время: 1 сек. Память: 16 Мб Сложность: 68%)

Существует множество игр, которые называются «игра в слова». В одной из вариаций правила следующие: выбирается длинное слово, после чего два игрока пытаются вспомнить все слова, которые можно составить, используя некоторые буквы загаданного слова. После этого они по очереди называют придуманные слова (называть одно слово два раза запрещается). Если первый игрок назвал больше слов, то он побеждает, если у обоих игроков слова закончились одновременно, засчитывается ничья, в оставшемся случае побеждает второй.

Оказывается, в этой игре важно не только знать много слов, но и придерживаться правильной стратегии. Напишите программу, которая будет узнавать, кто победит, если оба игрока будут играть идеально, если первый игрок будет играть оптимально, а второй - наихудшим образом, и если первый игрок будет поддаваться. При этом можно считать, что, придумав слова, игроки записывают их на бумагу, и каждый видит записи предыдущего. Если на ходу того игрока, который поддается, у него остаются не упоминавшиеся ранее слова, он обязан назвать одно из них.

Входные данные

В первой строке входного файла INPUT.TXT записано загаданное слово. Затем описываются слова, которые знает первый игрок - на отдельной строке целое число n1 (0 ≤ n1 ≤ 10000), за которым следуют n1 слов по одному на строке. После этого задается число n2 слов, известных второму игроку, и описываются сами эти слова в таком же формате. Все слова состоят из маленьких букв латинского алфавита, а их длины не превосходят 100 символов.

Выходные данные

В выходной файл OUTPUT.TXT выведите три числа по одному на строке - ответы для случаев, когда оба игрока играют оптимально и когда поддаются первый и второй игроки соответственно: номер выигрывающего игрока и 0 в случае ничьи.

Примеры

INPUT.TXTOUTPUT.TXT
1internationalization
6
zone
oil
rent
impression
noir
trail
7
teal
creativity
rent
rain
oil
zealot
zone
0
2
1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483