← 返回题目列表

Codeforces · 2201/G

G. Codeforces 启发式竞赛 1001

中文机器翻译题面 查看原题

有一个由 $$$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$$$。

请在维度为 $$$n \times n$$$ 的斑马图中找到满足以下条件的顶点子集 $$$S$$$。

  • 由子集 $$$S$$$ 导出的图 $$$^{\text{∗}}$$$ 与至少 $$$\left\lfloor{\frac{n^2}{e}}\right\rfloor$$$ 顶点 $$$^{\text{†}}$$$ 的循环图同构。

可以证明,在该问题的约束下存在这样的顶点子集。

$$$^{\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=5$$$;
  • 第二个输入文件有 $$$n=1001$$$。

对于此问题,黑客已被禁用。

输出

输出 $$$n$$$ 行,每行包含一个长度为 $$$n$$$ 的字符串 $$$s_i$$$ ,表示图形的第 $$$i$$$ 行。如果顶点 $$$(r,c)$$$ 是 $$$S$$$ 的元素,则 $$$s_r$$$ 的第 $$$c$$$ 个字母应该是 '1'。否则,$$$s_r$$$ 的第 $$$c$$$ 个字母应该是 '0'.

如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

5

输出
复制

01110
11011
10001
11011
01110

注意

对于示例输出,与子集 $$$S$$$ 对应的归纳图如下所示。

该图与由 $$$16$$$ 顶点组成的循环图 $$$C_{16}$$$ 同构。由于 $$$16 \ge \left\lfloor{\frac{n^2}{e}}\right\rfloor = 9$$$,输出满足问题的条件。