Дан граф из $$$n^2$$$ вершин, где вершины помечены целыми парами $$$(r,c)$$$ так, что $$$1 \le r,c \le n$$$. Вершины $$$(r_1,c_1)$$$ и $$$(r_2,c_2)$$$ непосредственно соединены тогда и только тогда, когда $$$(r_1-r_2)^2+(c_1-c_2)^2=\color{red}{13}$$$. Этот граф называется зебровым графом размерности $$$n \times n$$$.
Пожалуйста, найдите подмножество вершин $$$S$$$ в зебровом графе размерности $$$n \times n$$$, которое удовлетворяет следующему условию.
Можно показать, что такое подмножество вершин существует в условиях этой задачи.
$$$^{\text{∗}}$$$Индуцированный граф подмножества вершин $$$X$$$ — это граф, который содержит все вершины из $$$X$$$ и все ребра, оба конца которых находятся в $$$X$$$.
$$$^{\text{†}}$$$Здесь $$$e$$$ — математическая константа, равная пределу $$$\lim \limits_{n \to \infty} \left ({1 + \frac{1}{n}} \right )^n \approx 2.71828182$$$. Обратите внимание, что значение $$$\frac{1}{e}$$$ примерно равно $$$0.36787944$$$.
Первая и единственная строка ввода содержит одно целое число $$$n$$$ ($$$n\in \{5,1001\}$$$).
Для этой задачи есть только два теста:
Взломы для этой задачи отключены.
Выведите $$$n$$$ строк, каждая из которых содержит строку $$$s_i$$$ длиной $$$n$$$, обозначающую $$$i$$$-ю строку графа.
Если вершина $$$(r,c)$$$ является элементом $$$S$$$, то $$$c$$$-я буква $$$s_r$$$ должна быть '1'. В противном случае $$$c$$$-я буква $$$s_r$$$ должна быть '0'.
Если существует несколько решений, выведите любое из них.
5
01110 11011 10001 11011 01110
Для примера вывода индуцированный граф, соответствующий подмножеству $$$S$$$, показан ниже.
Этот граф изоморфен циклическому графу $$$C_{16}$$$, состоящему из $$$16$$$ вершин. Поскольку $$$16 \ge \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9$$$, вывод удовлетворяет условию задачи.
| Codeforces Round 1082 (Div. 1) |
|---|
| Закончено |
