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

省选/NOI-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There is a visualizer available for this problem. You can view it using this link.

Hacks are disabled on this problem.

This is the Easy Version of the problem. The only difference between the two versions is the constraints on nn and kk.

Verity has a grid of nn rows and nn columns. The rows are numbered from 11 to nn from top to bottom, and the columns are numbered from 11 to nn from left to right. The cell on row pp and column qq is denoted by (p,q)(p, q).

Verity also has a robot, Circuity, with extremely simple functionality. Verity must program Circuity so it can automatically locate specific cells on the grid, while ensuring these cells stay hidden from foreign robots.

There are two phases in this problem.

Phase 1: Verity (Encoding)

In this phase, Verity tries to encode a given cell on the grid.

Verity receives a target cell (r,c)(r, c), and he assigns a binary value (00 or 11) to each cell of the grid. On cells with value 11, beacons that broadcast signal will be placed, while cells with value 00 remain empty.

However, he believes that using too few beacons will make it easy for foreigners to also locate the target cell. Therefore, he has decided that it is safest to use at most kk zeros.

Phase 2: Circuity (Decoding)

In this phase, Circuity tries to find the cell Verity encoded, based on the grid he created. However, Circuity is unable to process large grids efficiently.

At each moment of time, Circuity suspects that the target cell lies in the subgrid bounded by the two cells (x0,y0)(x_0, y_0) and (x1,y1)(x_1, y_1). Initially, (x0,y0)=(1,1)(x_0, y_0) = (1, 1) and (x1,y1)=(n,n)(x_1, y_1) = (n, n).

Circuity locates the encoded cell by making exactly 2n−22n-2 decisions, one after another. Each decision works as follows.

Circuity can sense the number of beacons in the current subgrid. Let this number be SS. Formally, SS is the number of cells with value 11 inside the subgrid bounded by the cells (x0,y0)(x_0, y_0) and (x1,y1)(x_1, y_1).

Based solely on SS, it will choose exactly one of the following actions:

  • Action U: increase x0x_0 by 11
  • Action L: increase y0y_0 by 11
  • Action D: decrease x1x_1 by 11
  • Action R: decrease y1y_1 by 11

Note that this decision does not rely on previous decisions, and it cannot directly rely on the values of x0,x1,y0x_0, x_1, y_0 or y1y_1. Circuity is memoriless, and the only parameter when making a decision must be SS in the current moment.

If at any point x0>x1x_0 \gt x_1 or y0>y1y_0 \gt y_1, the program bugs out and Circuity is unsuccessful.

The cell Verity encoded in this grid was some cell (r,c)(r, c). After all 2n−22n-2 decisions, it must hold that x0=x1=rx_0 = x_1 = r and y0=y1=cy_0 = y_1 = c.

There exist only two tests:

  • n=3n = 3 and k=9k = 9;
  • n=20n = 20 and k=24k = \color{red}{24}.

本题提供一个可视化工具,您可通过此链接查看。

本题禁用 Hack 功能。

本题为该问题的简易版本。两个版本之间唯一的区别在于 nn 和 kk 的约束条件。

Verity 拥有一个 nn 行 nn 列的网格。行从上到下编号为 11 至 nn,列从左到右编号为 11 至 nn。第 pp 行第 qq 列的单元格记作 (p,q)(p, q)。

Verity 还拥有一台名为 Circuity 的机器人,其功能极其简单。Verity 必须对 Circuity 进行编程,使其能自动定位网格中特定的单元格,同时确保这些单元格对其他外部机器人保持隐藏。

本问题分为两个阶段。

第一阶段:Verity(编码)

在此阶段,Verity 尝试对给定的网格单元格进行编码。

Verity 接收一个目标单元格 (r,c)(r, c),并为网格中的每个单元格分配一个二进制值(00 或 11)。值为 11 的单元格上将放置广播信号的信标,而值为 00 的单元格则保持空置。

然而,Verity 认为使用过少的信标会使外部机器人也容易定位目标单元格。因此,他决定最安全的做法是至多使用 kk 个零(即网格中值为 00 的单元格数量不超过 kk)。

第二阶段:Circuity(解码)

在此阶段,Circuity 尝试根据 Verity 构建的网格找出被编码的目标单元格。但 Circuity 无法高效处理大规模网格。

在任意时刻,Circuity 怀疑目标单元格位于以两个单元格 (x0,y0)(x_0, y_0) 和 (x1,y1)(x_1, y_1) 为对角顶点的子网格内。初始时,(x0,y0)=(1,1)(x_0, y_0) = (1, 1),(x1,y1)=(n,n)(x_1, y_1) = (n, n)。

Circuity 通过恰好 2n−22n-2 次连续决策来定位被编码的单元格。每次决策按如下方式进行:

Circuity 可感知当前子网格中信标的数量,记为 SS。形式化地,SS 即子网格(由单元格 (x0,y0)(x_0, y_0) 和 (x1,y1)(x_1, y_1) 界定)中值为 11 的单元格个数。

Circuity 仅依据当前的 SS 值,从以下四个动作中恰好选择一个执行:

  • 动作 U:将 x0x_0 增加 11
  • 动作 L:将 y0y_0 增加 11
  • 动作 D:将 x1x_1 减少 11
  • 动作 R:将 y1y_1 减少 11

注意:该决策不依赖于先前的任何决策,也不能直接依赖 x0x_0、x1x_1、y0y_0 或 y1y_1 的当前值。Circuity 是无记忆的,其做决策时唯一允许的参数只能是当前时刻的 SS。

若在任意时刻出现 x0>x1x_0 > x_1 或 y0>y1y_0 > y_1,程序将崩溃,Circuity 定位失败。

Verity 在该网格中所编码的目标单元格为某个 (r,c)(r, c)。经过全部 2n−22n-2 次决策后,必须满足 x0=x1=rx_0 = x_1 = r 且 y0=y1=cy_0 = y_1 = c。

本题仅有两组测试数据:

  • n=3n = 3 且 k=9k = 9;
  • n=20n = 20 且 k=24k = \color{red}{24}。

输入格式

The only input contains one integer nn.

It is guaranteed that n=3n = 3 in the example, and n=20n = 20 in the only main test.

唯一的输入包含一个整数 nn。

保证示例中 n=3n = 3,而唯一的主要测试用例中 n=20n = 20。

输出格式

  • For Phase 11:

Output n2n^2 binary grids.

The ii-th grid is the grid Verity should choose when the target is (r,c)(r, c), where r=⌊i−1n⌋+1r = \lfloor \frac{i-1}{n} \rfloor + 1 and c=((i−1) mod n)+1c = ((i-1) \bmod n) + 1.

In other words, the first grid corresponds to target (1,1)(1,1), the second grid corresponds to target (1,2)(1,2), the (n+1)(n+1)-th grid corresponds to target (2,1)(2,1), and so on.

Each grid must contain at most kk zeros.

  • For Phase 22:

Output a sequence of n2+1n^2 + 1 characters: a0,a1,a2,…,an2a_0, a_1, a_2, \ldots, a_{n^2}. Each character must be one of U, D, L, or R. The ii-th character means that if S=iS=i, then Circuity performs action aia_i.

  • 第一阶段:

输出 n2n^2 个二进制网格。

第 ii 个网格是当目标位置为 (r,c)(r, c) 时 Verity 应选择的网格,其中 r=⌊i−1n⌋+1r = \lfloor \frac{i-1}{n} \rfloor + 1,c=((i−1) mod n)+1c = ((i-1) \bmod n) + 1。

换言之,第一个网格对应目标 (1,1)(1,1),第二个网格对应目标 (1,2)(1,2),第 (n+1)(n+1) 个网格对应目标 (2,1)(2,1),依此类推。

每个网格中最多包含 kk 个 0。

  • 第二阶段:

输出一个长度为 n2+1n^2 + 1 的字符序列:a0,a1,a2,…,an2a_0, a_1, a_2, \ldots, a_{n^2}。每个字符必须是 U、D、L 或 R 中的一个。第 ii 个字符表示:若 S=iS = i,则 Circuity 执行动作 aia_i。

输入输出样例

  • 输入#1

    3

    输出#1

    111
    111
    001
    
    011
    111
    100
    
    110
    110
    110
    
    010
    111
    111
    
    111
    111
    111
    
    010
    111
    101
    
    111
    111
    110
    
    111
    011
    111
    
    011
    010
    111
    
    DURLDULRUU

说明/提示

Consider the third grid as an example. The target cell is (1,3)(1,3).

Verity chooses the following grid:

110110110

The action sequence is:

DURLDULRUU

Initially, Circuity examines the subgrid bounded by (1,1)(1,1) and (3,3)(3,3).

It must locate cell (1,3)(1,3), so it will make 2⋅3−2=42 \cdot 3 - 2 = 4 decisions.

  • Decision 1: there are S=6S=6 ones in the current subgrid, so Circuity performs action a6=La_6=\mathtt{L}.

    The new subgrid becomes [(1,2),(3,3)][(1,2),(3,3)].

  • Decision 2: there are S=3S=3 ones in the current subgrid, so Circuity performs action a3=La_3=\mathtt{L}.

    The new subgrid becomes [(1,3),(3,3)][(1,3),(3,3)].

  • Decision 3: there are S=0S=0 ones in the current subgrid, so Circuity performs action a0=Da_0=\mathtt{D}.

    The new subgrid becomes [(1,3),(2,3)][(1,3),(2,3)].

  • Decision 4: there are again S=0S=0 ones in the current subgrid, so Circuity performs action a0=Da_0=\mathtt{D}.

    The new subgrid becomes [(1,3),(1,3)][(1,3),(1,3)].

After all decisions, Circuity ends up at cell (1,3)(1,3), which is indeed the target cell.

以第三个网格为例,目标单元格为 (1,3)(1,3)。

Verity 选择了如下网格:

110110110

对应的操作序列为:

DURLDULRUU

初始时,Circuity 检查由 (1,1)(1,1) 和 (3,3)(3,3) 所界定的子网格。

它必须定位单元格 (1,3)(1,3),因此将做出 2⋅3−2=42 \cdot 3 - 2 = 4 次决策。

  • 决策 1:当前子网格中包含 S=6S=6 个 1,因此 Circuity 执行操作 a6=La_6=\mathtt{L}。

    新的子网格变为 [(1,2),(3,3)][(1,2),(3,3)]。

  • 决策 2:当前子网格中包含 S=3S=3 个 1,因此 Circuity 执行操作 a3=La_3=\mathtt{L}。

    新的子网格变为 [(1,3),(3,3)][(1,3),(3,3)]。

  • 决策 3:当前子网格中包含 S=0S=0 个 1,因此 Circuity 执行操作 a0=Da_0=\mathtt{D}。

    新的子网格变为 [(1,3),(2,3)][(1,3),(2,3)]。

  • 决策 4:当前子网格中再次包含 S=0S=0 个 1,因此 Circuity 执行操作 a0=Da_0=\mathtt{D}。

    新的子网格变为 [(1,3),(1,3)][(1,3),(1,3)]。

完成全部决策后,Circuity 最终停留在单元格 (1,3)(1,3),这确实是目标单元格。

输入解题思路,AI测评打分。不知道怎么写?

首页