← 返回题目列表

AtCoder · agc077_e

E. 哈密顿路径反演

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

分数: 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,因此满足条件。 给出了第二个问题的