CF2201G.Codeforces Heuristic Contest 1001

There is a graph of $n^2$ vertices, where vertices are labeled by integer pairs $(r,c)$ such that $1 \le r,c \le n$. Vertices $(r_1,c_1)$ and $(r_2,c_2)$ are directly connected if and only if $(r_1-r_2)^2+(c_1-c_2)^2=\color{red}{13}$. This graph is called the Zebra Graph of dimensions $n \times n$.

Please find a subset of vertices $S$ in the Zebra Graph of dimensions $n \times n$, which satisfies the following condition.

• The graph induced$^{\text{∗}}$ by the subset $S$ is isomorphic to a cycle graph of at least $\left\lfloor{\frac{n^2}{e}}\right\rfloor$ vertices$^{\text{†}}$.

It can be shown that such a subset of vertices exists under the constraints of this problem.

$^{\text{∗}}$The induced graph of a subset of vertices $X$ is a graph that contains all vertices in $X$ and all edges whose both endpoints are in $X$.

$^{\text{†}}$Here, $e$ is the mathematical constant equal to the limit $\lim \limits_{n \to \infty} \left ({1 + \frac{1}{n}} \right )^n \approx 2.71828182$. Note that the value of $\frac{1}{e}$ is approximately $0.36787944$.

存在一个包含 $n^2$ 个顶点的图，其顶点用整数对 $(r,c)$ 标记，其中 $1 \le r,c \le n$。当且仅当 $(r_1-r_2)^2+(c_1-c_2)^2=\color{red}{13}$ 时，顶点 $(r_1,c_1)$ 与 $(r_2,c_2)$ 直接相连。该图称为 $n \times n$ 维的“斑马图”（Zebra Graph）。

请在 $n \times n$ 维斑马图中找出一个顶点子集 $S$，使其满足如下条件：

• 由子集 $S$ 所导出的子图$^{\text{∗}}$ 同构于一个至少包含 $\left\lfloor{\frac{n^2}{e}}\right\rfloor$ 个顶点的环图（cycle graph）$^{\text{†}}$。

可以证明，在本题的约束条件下，这样的顶点子集 $S$ 必然存在。

$^{\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$。

The first and only line of input contains a single integer $n$ ($n\in {5,1001}$).

There are only two input files for this problem:

• The first input file (the example input) has $n=5$;
• The second input file has $n=1001$.

Hacks are disabled for this problem.

输入仅有一行，包含一个整数 $n$（$n\in \{5,1001\}$）。

本题仅有两个输入文件：

• 第一个输入文件（样例输入）中 $n=5$；
• 第二个输入文件中 $n=1001$。

本题禁用 Hack 功能。

Output $n$ lines, each containing a string $s_i$ of length $n$ denoting the $i$-th row of the graph. If the vertex $(r,c)$ is an element of $S$, then the $c$-th letter of $s_r$ should be '1'. Otherwise, the $c$-th letter of $s_r$ should be '0'.

If there are multiple solutions, print any of them.

输出 $n$ 行，每行包含一个长度为 $n$ 的字符串 $s_i$，表示图的第 $i$ 行。若顶点 $(r,c)$ 属于集合 $S$，则 $s_r$ 的第 $c$ 个字符应为 '1'；否则，$s_r$ 的第 $c$ 个字符应为 '0'。

若存在多个解，输出任意一个即可。

For the example output, the induced graph corresponding to the subset $S$ is shown below.

This graph is isomorphic to the cycle graph $C_{16}$ consisting of $16$ vertices. As $16 \ge \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9$, the output satisfies the problem's condition.

对于示例输出，子集 $S$ 对应的导出子图如下所示。

该图同构于由 $16$ 个顶点构成的环图 $C_{16}$。由于 $16 \ge \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9$，因此该输出满足题目的条件。