Игра в слова

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

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

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

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

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

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

Примеры

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

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