Вам даны $$$n^2$$$ карточек со значениями от $$$0$$$ до $$$n^2-1$$$. Вам необходимо расположить их в ячейках матрицы размера $$$n$$$ на $$$n$$$, так чтобы в каждой ячейке находилась ровно одна карточка.
MEX (минимальное исключенное значение) подматрицы$$$^{\text{∗}}$$$ определяется как наименьшее целое неотрицательное число, которое не встречается в подматрице.
Ваша задача — расположить карточки так, чтобы сумма значений MEX по всем $$$\left(\frac{n(n+1)}{2}\right)^2$$$ подматрицам была максимальной.
$$$^{\text{∗}}$$$Подматрица матрицы размером $$$n$$$ на $$$n$$$ задается четыремя индексами $$$l_1, r_1, l_2, r_2$$$, удовлетворяющими $$$1\le l_1\le r_1\le n$$$ и $$$1\le l_2\le r_2\le n$$$. Элемент в $$$i$$$-й стррке и $$$j$$$-м столбце матрицы принадлежит подматрице, если и только если $$$l_1\le i\le r_1$$$ и $$$l_2\le j\le r_2$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 500$$$) — длина стороны квадратной матрицы.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Для каждого набора входных данных выведите $$$n$$$ строк, каждая из которых содержит $$$n$$$ целых чисел, представляющих элементы матрицы.
Если есть несколько решений, вы можете вывести любое из них.
223
0 1 2 3 8 4 5 6 0 1 7 2 3
В первом наборе входных данных одно из допустимых расположений:
| 0 | 1 |
| 2 | 3 |
Всего имеется $$$9$$$ подматриц, и $$$4$$$ из них с ненулевым MEX показаны ниже:
| 0 |
| 0 | 1 |
| 0 |
| 2 |
| 0 | 1 |
| 2 | 3 |
Сумма MEX по всем подматрицам составляет $$$1+2+1+4 = 8$$$.
Можно показать, что другие расположения не имеют большей суммы значений MEX.
| Codeforces Round 1024 (Div. 1) |
|---|
| Закончено |
