分数: 1000 点
问题陈述
考虑写 0 or 1 在 a 的每个顶点上 4\times 500 网格图。巧妙地写下这些值,以便对于每个 N=0,1,\ldots,999899,999900,满足以下条件。
- 网格图上存在一条哈密顿路径,使得沿该路径写在顶点上的数字序列的反转计数为 N.
![]()
一个例子 3\times 4。通过这次作业, N = 10, 11, \ldots, 20 是可以实现的。
这是一个 互动 问题。 问题陈述中的参数固定为 H=4,W=500,Q=200.
您和法官执行以下步骤。步骤包括阶段 1 和相位 2;阶段 首先执行 1 ,紧接着执行 Phase 2.
(阶段 1)
输出 H\times W 矩阵 A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) 其中每个元素是 0 or 1.
(阶段 2)
解决以下问题 Q 次。
法官给你一个整数 N.
考虑 H-行 W- 列网格。细胞 (i,j),位于 i从顶部开始的第行和 j- 从左边算起的第列,有整数 A_{i,j} 。
查找路径 P 长度 HW 从任何单元格开始,重复移动到相邻单元格(上、下、左或右),访问所有单元格 HW 单元格恰好一次,并在任何单元格结束,从而满足以下条件。
- 长度序列的倒数计数 HW 通过列出写在访问的单元格上的整数获得 P 的顺序是 N.
约束
- H=4,W=500,Q=200
- 0\leq N\leq 999900
- 所有输入值均为整数。
互动
这是一个交互问题。
首先, H,W,Q 由标准输入给出。
H W Q
(阶段 1)
输出 H\times W 矩阵 A=(A_{i,j})\ (1\leq i\leq H,1\leq j\leq W) 其中每个元素是 0 or 1,结束 H 行。
的
树的 i- 第行应包含 A_{i,1}A_{i,2}\ldots A_{i,W} 作为长度的字符串 W 组成 0 和 1.
A_{1,1}A_{1,2}\ldots A_{1,W}
A_{2,1}A_{2,2}\ldots A_{2,W}
\vdots
A_{H,1}A_{H,2}\ldots A_{H,W}
(阶段 2)
解决问题 Q 次。对于每个问题,首先是一个整数 N 由标准输入给出。
N
(注意:如果您对上一个问题的回答不正确,或者如果 A 或路径以不正确的格式输出,则改为 N, -1 从此处的标准输入给出。在这种情况下,请立即正常终止程序。但是,如果第一次给出不正确的输出 Q第一个问题,不会给出进一步的输入。)
然后,输出一个路径 P 满足条件,其中 i第一个访问的单元格是 (x_i, y_i),格式如下:
x_1 y_1
x_2 y_2
\vdots
x_{HW} y_{HW}
x_i 和 y_i 必须满足以下条件。
- 1\leq x_i\leq H, 1\leq y_i\leq W.
- (x_i,y_i)\neq (x_j,y_j) if i\neq j.
- |x_i-x_{i+1}|+|y_i-y_{i+1}|=1 为 i=1,2,\ldots,HW-1.
- 序列的反转计数 (A_{x_1,y_1}, A_{x_2,y_2},\ldots,A_{x_{HW},y_{HW}}) is N.
注释
- 如果您收到
-1作为判断输入,立即正常终止程序。如果您终止,判决将是 WA;否则,判决为不确定的。 - 在每个输出中,在末尾包含换行符并刷新标准输出。否则,判决可能是 TLE.
- 输出中额外的换行符被视为格式错误;不包括它们。
- 完成阶段后立即终止程序 2。否则,判决是不确定的。
示例交互
以下是该案例的交互示例 H=3,W=4,Q=2.
该示例不满足约束条件,不纳入判断。
| 输入 | 输出 | 说明 给出了 |
|---|---|---|
3 4 2 | H,W,Q 。 给出了第一个问题的 | |
1101 0110 1010 | 输出 A=\begin{pmatrix} 1&1&0&1 \\ 0&1&1&0 \\ 1&0&1&0 \end{pmatrix}. | |
10 | N 。 | |
3 2 3 3 3 4 2 4 1 4 1 3 2 3 2 2 1 2 1 1 2 1 3 1 | 输出路径 (3,2)\to(3,3)\to(3,4)\to(2,4)\to(1,4)\to(1,3)\to(2,3)\to(2,2)\to(1,2)\to(1,1)\to(2,1)\to(3,1)。沿着这条路径访问的单元格上写入的整数序列是 (0,1,0,0,1,0,1,1,1,1,0,1),该序列的反转计数为 10,因此满足条件。 给出了第二个问题的 | |
15 | N 。 | |
1 1 2 1 3 1 3 2 3 3 3 4 2 4 2 3 2 2 1 2 1 3 1 4 | 输出路径 (1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)\to(3,4)\to(2,4)\to(2,3)\to(2,2)\to(1,2)\to(1,3)\to(1,4)。沿着这条路径访问的单元格上写入的整数序列是 (1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1),该序列的反转计数为 15,因此满足条件。 给出了第二个问题的 |