Codeforces Round 963 (Div. 2) |
---|
Закончено |
Дана матрица $$$a$$$ размера $$$n \times m$$$, каждая ячейка которой содержит неотрицательное целое число. Число, находящееся на пересечении $$$i$$$-й строки и $$$j$$$-го столбца матрицы, называется $$$a_{i,j}$$$.
Определим $$$f(i)$$$ и $$$g(j)$$$ как XOR всех чисел в $$$i$$$-й строке и $$$j$$$-м столбце соответственно. За одну операцию вы можете либо:
В этом примере, когда мы применяем операцию к столбцу $$$2$$$, все элементы в этом столбце изменяются следующим образом:
Вы можете применять операции любое количество раз. Затем мы вычислим $$$\textit{красоту}$$$ финальной матрицы, суммируя абсолютные разности между всеми парами её соседних ячеек.
Более формально, $$$\textit{красота}(a) = \sum|a_{x,y} - a_{r,c}|$$$ для всех ячеек $$$(x, y)$$$ и $$$(r, c)$$$, если они соседние. Две ячейки считаются соседними, если они имеют общую сторону.
Найдите минимальную $$$\textit{красоту}$$$ среди всех достижимых матриц.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 250$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 15$$$) — количество строк и столбцов матрицы $$$a$$$ соответственно.
Далее идут $$$n$$$ строк, каждая из которых содержит $$$m$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$0 \le a_{i,j} < 2^{20}$$$) — описание матрицы $$$a$$$.
Гарантируется, что сумма $$$(n^2 + m^2)$$$ по всем наборам входных данных не превышает $$$500$$$.
Для каждого набора входных данных выведите одно целое число $$$b$$$ — наименьшая возможная $$$\textit{красота}$$$ матрицы.
41 21 32 30 1 05 4 42 30 2 44 5 13 31 2 34 5 67 8 9
1 3 13 24
Обозначим $$$r(i)$$$ как операцию первого типа, примененную к $$$i$$$-й строке, и $$$c(j)$$$ как операцию второго типа, примененную к $$$j$$$-му столбцу.
В первом наборе входных данных вы можете применить операцию $$$c(1)$$$, которая присвоит $$$a_{1,1} := 1 \oplus 3 = 2$$$. Затем мы получим эту матрицу:
2 | 3 |
Во втором наборе входных данных вы можете применить операцию $$$r(1)$$$, которая присвоит:
Финальная матрица после выполнения операции:
5 | 5 | 4 |
5 | 4 | 4 |
В третьем наборе входных данных лучший способ достичь минимальной $$$\textit{красота}$$$ — применить три операции: $$$c(3)$$$, $$$r(2)$$$ и $$$c(2)$$$. Финальная матрица:
0 | 4 | 6 |
4 | 5 | 6 |
Название |
---|