CF2261F1 Plegma II: Ask Me Any Cell (Easy Version)

本题提供了可视化工具，你可以通过[此链接](https://codeforces.com/assets/contests/2261/F_16d6cdc51811e4c62b25c3.html)查看。 本题不支持 Hack。 这是本题的 Easy 版本，两种版本间唯一的区别是 $n$ 和 $k$ 的约束不同。 Verity 有一个由 $n$ 行 $n$ 列组成的网格。行从上到下依次编号为 $1$ 到 $n$，列从左到右依次编号为 $1$ 到 $n$。第 $p$ 行第 $q$ 列的格子记作 $(p, q)$。 Verity 还拥有一个功能极其简单的机器人“Circuity”。Verity 需要为 Circuity 编写程序，使其能自动定位网格上的特定格子，同时保证这些目标格子不会被其他外来机器人发现。 本题分为两个阶段。 **阶段一：Verity（编码）** 在这个阶段，Verity 需要对给定的目标格子进行编码。 Verity 每次会得到一个目标格子 $(r, c)$，并为网格中的每个格子分配一个二进制数值（$0$ 或 $1$）。值为 $1$ 的格子将放置信标用于发送信号，而值为 $0$ 的格子留空。 但 Verity 认为信标太少容易让外人也找到目标格子，因此他决定每次最多只能使用 $k$ 个 $0$。 **阶段二：Circuity（解码）** 在这个阶段，Circuity 需要根据 Verity 编码后的网格找到目标格子。但 Circuity 不能高效处理大的网格。 在每个时刻，Circuity 都怀疑目标格子位于由 $(x_0, y_0)$ 与 $(x_1, y_1)$ 所围成的子矩形中。起始时，$(x_0, y_0) = (1, 1)$，$(x_1, y_1) = (n, n)$。 Circuity 需要通过连续 $2n-2$ 次决策来定位目标格子。每次决策具体如下： Circuity 能感知当前子矩形中的信标数量，记为 $S$。即，$S$ 是由格点 $(x_0, y_0)$ 和 $(x_1, y_1)$ 围成的子矩阵中，值为 $1$ 的格子的数量。 Circuity 仅根据 $S$，从以下操作中恰好选择一个： - 操作 U：将 $x_0$ 加 $1$ - 操作 L：将 $y_0$ 加 $1$ - 操作 D：将 $x_1$ 减 $1$ - 操作 R：将 $y_1$ 减 $1$ 注意，Circuity 的决策与之前的任何操作、以及 $x_0, x_1, y_0, y_1$ 的具体值均无关。Circuity 没有记忆功能，每步只能基于当前的 $S$ 做决策。 如果某一时刻出现 $x_0 > x_1$ 或 $y_0 > y_1$，程序将崩溃，Circuity 定位失败。 假定 Verity 编码的目标格子是 $(r, c)$。全部 $2n-2$ 步操作后，必须满足 $x_0 = x_1 = r$，$y_0 = y_1 = c$。 仅有两个测试点： - $n = 3$，$k = 9$； - $n = 20$，$k = \color{red}{24}$。

唯一一行为一个整数 $n$。 保证在样例中 $n=3$，在正式测试点中 $n=20$。

- **阶段一（编码）：** 输出 $n^2$ 个二进制网格。 第 $i$ 个网格是 Verity 针对 $(r, c)$ 编码的结果，其中 $r = \lfloor\frac{i-1}{n}\rfloor+1$，$c = ((i-1) \bmod n) + 1$。 换言之，第一个网格对应目标格子 $(1,1)$，第二个网格对应 $(1,2)$，第 $n+1$ 个网格对应 $(2,1)$，以此类推。 每个网格中最多只能有 $k$ 个 $0$。 - **阶段二（解码）：** 输出一个总长为 $n^2+1$ 的操作序列：$a_0, a_1, a_2, \ldots, a_{n^2}$。每个字符只能是 U、D、L、R 之一。第 $i$ 个字符表示：当 $S=i$ 时，Circuity 应执行操作 $a_i$。

以第 3 个网格为例，目标格子为 $(1,3)$。 Verity 可以选择如下网格： ``` 110 110 110 ``` 操作序列为： ``` DURLDULRUU ``` 初始时，Circuity 考察由 $(1,1)$ 与 $(3,3)$ 围成的整个网格。 需要定位格子 $(1,3)$，需操作 $2 \times 3 - 2 = 4$ 步。 - 第 1 步：当前子网格内有 $S=6$ 个 $1$，执行 $a_6=\mathtt{L}$，新子网格为 $[(1,2),(3,3)]$。 - 第 2 步：当前子网格内有 $S=3$ 个 $1$，执行 $a_3=\mathtt{L}$，新子网格为 $[(1,3),(3,3)]$。 - 第 3 步：当前子网格内有 $S=0$ 个 $1$，执行 $a_0=\mathtt{D}$，新子网格为 $[(1,3),(2,3)]$。 - 第 4 步：当前子网格内有 $S=0$ 个 $1$，执行 $a_0=\mathtt{D}$，新子网格为 $[(1,3),(1,3)]$。 操作结束，Circuity 成功定位到 $(1,3)$，正好为目标格子。 由 ChatGPT 5 翻译