| Codeforces Round 1093 (Div. 1) |
|---|
| Закончено |
Рассмотрим шахматную доску (таблицу) размера $$$n \times n$$$. Нужно расставить на этой доске как можно больше шахматных фигур. Эти фигуры ведут себя следующим образом: если обозначить левую верхнюю клетку как $$$(1,1)$$$, то фигура, стоящая в клетке $$$(i,j)$$$, может атаковать каждую клетку $$$(x,y)$$$, такую, что $$$x \ge i$$$ и $$$y \ge j$$$, кроме самой клетки $$$(i,j)$$$.
Например, на доске $$$10 \times 10$$$ фигура, стоящая в $$$(3,4)$$$, может атаковать клетки, выделенные ниже:
Дана шахматная доска с некоторыми расставленными на ней фигурами. Назовём клетку хорошей, если количество фигур, атакующих эту клетку, чётно.
Постройте конфигурацию фигур так, чтобы каждая клетка была хорошей, независимо от того, стоит ли в ней фигура или нет, и при этом на доске было как минимум $$$\lfloor \frac{n^2}{10} \rfloor \cdot 3$$$ фигур.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных дано целое число $$$n$$$ ($$$1 \le n \le 5000$$$).
Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$25\,000\,000 = 5000^2$$$.
Для каждого набора входных данных выведите $$$n$$$ строк. В $$$i$$$-й строке выведите $$$n$$$ целых чисел, разделённых пробелами, где $$$1$$$ означает, что в этой клетке стоит фигура, а $$$0$$$ означает, что фигуры нет.
$$$j$$$-е число в $$$i$$$-й строке соответствует клетке $$$(i,j)$$$.
1 3
0 0 1 0 1 1 1 0 1
Этот пример представляет собой шахматную доску размера $$$3 \times 3$$$, где каждая клетка хорошая.
Клетка $$$(3, 3)$$$ хорошая, потому что клетки с фигурами $$$(1, 3), (2, 3), (2, 2), (3, 1)$$$ атакуют её, и это количество равно 4, то есть чётно.
Клетка $$$(1, 3)$$$ хорошая, потому что её не атакует ни одна фигура, поэтому количество фигур, атакующих эту клетку, равно 0.
Клетка $$$(3, 2)$$$ хорошая, и обратите внимание, что для этой клетки требуется быть хорошей, даже несмотря на то, что в ней нет фигуры.
