Задача №111149. Нечестные турниры с выбыванием
На олимпиаде для 7-9 классов участники научились составлять некоторую сетку кругового турнира. Теперь вам предлагается организовать теннисный турнир с выбыванием.
Вам дана полная информация обо всех участниках соревнования. Она содержит результаты всех возможных матчей (для каждой пары участников известно, кто выиграет, если провести соответствующий матч). Теперь вы хотите подсчитать для каждого игрока, сколько существует возможных турниров с выбыванием и минимальным числом туров, в которых выигрывает именно этот игрок (турнир с выбыванием — это когда проигравший навсегда уходит из игры, его можно представить как бинарное дерево, числом туров тогда будет являться высота этого дерева).
Первая строка содержит два числа N и M — общее количество людей и число людей, для которых необходимо найти искомое число турниров (1 ≤ N ≤ 16).
В следующей строке содержатся номера самих игроков. Нумерация игроков ведется с единицы.
Далее содержится таблица N × N, описывающая исход игры между соответствующей парой людей (на j-ом месте в i-ой строке содержится 1, если i-ый игрок выиграет j-ого, и ноль в противном случае, на диагонали также находятся нули).
Для каждого игрока выведите одно число — искомое число турниров, в которых он может победить.
2 1
1
0 1
0 0
1
2 1
1
0 0
1 0
0
6 1
4
0 0 0 0 0 1
1 0 1 0 1 0
1 0 0 1 1 0
1 1 0 0 1 0
1 0 0 0 0 0
0 1 1 1 1 0
11
Подзадача 1. N ≤ 5. Решение оценивается в 30 баллов.
Подзадача 2. N ≤ 10. Решение оценивается в 30 баллов.
Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.