0275. Игра

Имя входного файла:	game.in
Имя выходного файла:	game.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Камень, ножницы, бумага — популярная детская игра на руках, известная во многих странах мира.
Иногда используется как методика случайного выбора персоны для какой-либо цели
wikipedia

Всем известны правила игры <<Камень, ножницы, бумага>>  – играющие одновременно показывают при помощи руки один из трёх знаков: камень, ножницы или бумагу.

При этом, победитель определяется по следующим правилам:

• Камень побеждает ножницы.
• Ножницы побеждают бумагу.
• Бумага побеждает камень.

Ничья засчитывается в ситуации, когда одновременно хотя бы один игрок показал <<камень>>, хотя бы один игрок показал <<бумагу>> и хотя бы один игрок показал <<ножницы>>.

Леонарду и его друзьям надоело играть в обычную версию этой игры, поэтому они решили придумать свою собственную. В их версии игры знаков будет не три, а целых n. Для каждой пары знаков они заранее определили, какой из знаков будет бить другой знак. Победившим объявляется игрок, знак которого не проигрывает ни одному из других знаков и выигрывает хотя бы у одного другого знака. Если таких людей несколько, то они все объявляются победителями. Если таких игроков нет, то объявляется ничья.

Друзья решили сыграть в новую версию игры и позвали своих друзей, в итоге получилось m человек. Каждый из них показал один из n знаков. Теперь перед ними возникла новая проблема  – определить, кто выиграл в этой игре. Так как они очень устали, они попросили вас помочь им.

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

В первой строке входного файла даны два целых числа n и m  – количество знаков и количество людей в игре соответственно (1 ≤ n, m ≤ 100). В следующих n строках задана матрица правил этой игры. На j-ой позиции i-ой строки находится число 1, если i-ый знак побеждает j-ый знак, и 0 иначе. Гарантируется, что на i-ой позиции в i-ой строки находится число 0. В последней строке входного файла задано m целых чисел a_i (1 ≤ a_i ≤ n)  – номер знака, который выбрал i-ый друг.

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

В единственной строке выходного файла выведите номера всех выигравших друзей в возрастающем порядке. В случае ничьей выведите единственное число -1.

Пример:

game.in	game.out
3 2 0 1 0 0 0 1 1 0 0 1 2	1
3 2 0 1 0 0 0 1 1 0 0 2 2	-1
3 3 0 1 0 0 0 1 1 0 0 1 2 3	-1

Источник: Первенство первокурсника ПетрГУ. Май 2012

Обсудить       Отправить решение



Версия для печати