Codeforces Round 553 (Div. 2) |
---|
Закончено |
У лицеиста Димы из Кремляндии есть таблица $$$a$$$ размера $$$n \times m$$$, заполненная целыми неотрицательными числами.
Он хочет в каждой строке выбрать ровно одно число так, чтобы побитовое исключающее ИЛИ выбранных чисел было строго больше нуля. Помогите ему!
Формально, он хочет выбрать последовательность чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_j \leq m$$$) так, чтобы выполнялось неравенство $$$a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0$$$, где $$$a_{i, j}$$$ — элемент таблицы в $$$i$$$-й строке и $$$j$$$-м столбце.
Здесь $$$x \oplus y$$$ обозначает операцию побитового исключающего ИЛИ чисел $$$x$$$ и $$$y$$$.
В первой строке записаны два целых числа $$$n$$$ и $$$m$$$, разделенных пробелом ($$$1 \leq n, m \leq 500$$$) — количество строк и столбцов в матрице $$$a$$$.
В следующих $$$n$$$ строках записано по $$$m$$$ целых чисел, разделенных пробелом: $$$j$$$-е число в $$$i$$$-й из этих строк обозначает $$$j$$$-й элемент $$$i$$$-й строки матрицы $$$a$$$, то есть $$$a_{i, j}$$$ ($$$0 \leq a_{i, j} \leq 1023$$$).
Если не существует способа выбрать в каждой строке таблицы одно число, чтобы их побитовое исключающее ИЛИ было строго больше нуля, выведите «NIE».
В противном случае выведите «TAK», и в следующей строке выведите $$$n$$$ целых чисел $$$c_1, c_2, \ldots c_n$$$, разделенных пробелами, ($$$1 \leq c_j \leq m$$$), чтобы выполнялось неравенство $$$a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0$$$.
Если существует более одного возможного ответа, вы можете вывести любой.
3 2 0 0 0 0 0 0
NIE
2 3 7 7 7 7 7 10
TAK 1 3
В первом примере все числа в матрице равны $$$0$$$, поэтому невозможно выбрать в каждой строке таблицы по одному числу так, чтобы их побитовое исключающее ИЛИ было строго больше нуля.
Во втором примере выбранные числа $$$7$$$ (первое число в первой строке) и $$$10$$$ (третье число во второй строке), $$$7 \oplus 10 = 13$$$, $$$13$$$ больше чем $$$0$$$, поэтому ответ найден.
Название |
---|