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 n and k.
Verity has a grid of n rows and n columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to n from left to right. The cell on row p and column q is denoted by (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), and he assigns a binary value (0 or 1) to each cell of the grid. On cells with value 1, beacons that broadcast signal will be placed, while cells with value 0 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 k 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) and (x1,y1). Initially, (x0,y0)=(1,1) and (x1,y1)=(n,n).
Circuity locates the encoded cell by making exactly 2n−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 S. Formally, S is the number of cells with value 1 inside the subgrid bounded by the cells (x0,y0) and (x1,y1).
Based solely on S, it will choose exactly one of the following actions:
- Action U: increase x0 by 1
- Action L: increase y0 by 1
- Action D: decrease x1 by 1
- Action R: decrease y1 by 1
Note that this decision does not rely on previous decisions, and it cannot directly rely on the values of x0,x1,y0 or y1. Circuity is memoriless, and the only parameter when making a decision must be S in the current moment.
If at any point x0>x1 or y0>y1, the program bugs out and Circuity is unsuccessful.
The cell Verity encoded in this grid was some cell (r,c). After all 2n−2 decisions, it must hold that x0=x1=r and y0=y1=c.
There exist only two tests:
- n=3 and k=9;
- n=20 and k=24.
本题提供一个可视化工具,您可通过此链接查看。
本题禁用 Hack 功能。
本题为该问题的简易版本。两个版本之间唯一的区别在于 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 的单元格数量不超过 k)。
第二阶段:Circuity(解码)
在此阶段,Circuity 尝试根据 Verity 构建的网格找出被编码的目标单元格。但 Circuity 无法高效处理大规模网格。
在任意时刻,Circuity 怀疑目标单元格位于以两个单元格 (x0,y0) 和 (x1,y1) 为对角顶点的子网格内。初始时,(x0,y0)=(1,1),(x1,y1)=(n,n)。
Circuity 通过恰好 2n−2 次连续决策来定位被编码的单元格。每次决策按如下方式进行:
Circuity 可感知当前子网格中信标的数量,记为 S。形式化地,S 即子网格(由单元格 (x0,y0) 和 (x1,y1) 界定)中值为 1 的单元格个数。
Circuity 仅依据当前的 S 值,从以下四个动作中恰好选择一个执行:
- 动作 U:将 x0 增加 1
- 动作 L:将 y0 增加 1
- 动作 D:将 x1 减少 1
- 动作 R:将 y1 减少 1
注意:该决策不依赖于先前的任何决策,也不能直接依赖 x0、x1、y0 或 y1 的当前值。Circuity 是无记忆的,其做决策时唯一允许的参数只能是当前时刻的 S。
若在任意时刻出现 x0>x1 或 y0>y1,程序将崩溃,Circuity 定位失败。
Verity 在该网格中所编码的目标单元格为某个 (r,c)。经过全部 2n−2 次决策后,必须满足 x0=x1=r 且 y0=y1=c。
本题仅有两组测试数据:
- n=3 且 k=9;
- n=20 且 k=24。
输入格式
The only input contains one integer n.
It is guaranteed that n=3 in the example, and n=20 in the only main test.
唯一的输入包含一个整数 n。
保证示例中 n=3,而唯一的主要测试用例中 n=20。
输出格式
- For Phase 1:
Output n2 binary grids.
The i-th grid is the grid Verity should choose when the target is (r,c), where r=⌊ni−1⌋+1 and c=((i−1)modn)+1.
In other words, the first grid corresponds to target (1,1), the second grid corresponds to target (1,2), the (n+1)-th grid corresponds to target (2,1), and so on.
Each grid must contain at most k zeros.
- For Phase 2:
Output a sequence of n2+1 characters: a0,a1,a2,…,an2. Each character must be one of U, D, L, or R. The i-th character means that if S=i, then Circuity performs action ai.
- 第一阶段:
输出 n2 个二进制网格。
第 i 个网格是当目标位置为 (r,c) 时 Verity 应选择的网格,其中 r=⌊ni−1⌋+1,c=((i−1)modn)+1。
换言之,第一个网格对应目标 (1,1),第二个网格对应目标 (1,2),第 (n+1) 个网格对应目标 (2,1),依此类推。
每个网格中最多包含 k 个 0。
- 第二阶段:
输出一个长度为 n2+1 的字符序列:a0,a1,a2,…,an2。每个字符必须是 U、D、L 或 R 中的一个。第 i 个字符表示:若 S=i,则 Circuity 执行动作 ai。
输入输出样例
输入#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).
Verity chooses the following grid:
110110110
The action sequence is:
DURLDULRUU
Initially, Circuity examines the subgrid bounded by (1,1) and (3,3).
It must locate cell (1,3), so it will make 2⋅3−2=4 decisions.
-
Decision 1: there are S=6 ones in the current subgrid, so Circuity performs action a6=L.
The new subgrid becomes [(1,2),(3,3)].
-
Decision 2: there are S=3 ones in the current subgrid, so Circuity performs action a3=L.
The new subgrid becomes [(1,3),(3,3)].
-
Decision 3: there are S=0 ones in the current subgrid, so Circuity performs action a0=D.
The new subgrid becomes [(1,3),(2,3)].
-
Decision 4: there are again S=0 ones in the current subgrid, so Circuity performs action a0=D.
The new subgrid becomes [(1,3),(1,3)].
After all decisions, Circuity ends up at cell (1,3), which is indeed the target cell.
以第三个网格为例,目标单元格为 (1,3)。
Verity 选择了如下网格:
110110110
对应的操作序列为:
DURLDULRUU
初始时,Circuity 检查由 (1,1) 和 (3,3) 所界定的子网格。
它必须定位单元格 (1,3),因此将做出 2⋅3−2=4 次决策。
-
决策 1:当前子网格中包含 S=6 个 1,因此 Circuity 执行操作 a6=L。
新的子网格变为 [(1,2),(3,3)]。
-
决策 2:当前子网格中包含 S=3 个 1,因此 Circuity 执行操作 a3=L。
新的子网格变为 [(1,3),(3,3)]。
-
决策 3:当前子网格中包含 S=0 个 1,因此 Circuity 执行操作 a0=D。
新的子网格变为 [(1,3),(2,3)]。
-
决策 4:当前子网格中再次包含 S=0 个 1,因此 Circuity 执行操作 a0=D。
新的子网格变为 [(1,3),(1,3)]。
完成全部决策后,Circuity 最终停留在单元格 (1,3),这确实是目标单元格。
输入解题思路,AI测评打分。不知道怎么写?