故事
A 图灵机 是计算理论中使用的理论计算机器。它通过以下方式执行计算 转换规则,更改其 内部状态 (机器内存中存储的值)和 头部位置的 符号 在一维磁带上,同时向左或向右移动头部。
F Corporation 正在开发一款仿照该机制的机器人。该机器人在二维网格板上运行,可以在跟随的同时上下左右移动 转换规则 更新其 内部状态 和 当前位置的颜色.
你的任务是设计机器人的 转换规则 以便它按顺序访问给定的目的地序列。由于开发成本与所使用的颜色和状态的数量之和成正比,因此希望尽可能地最小化该总和。
问题陈述
有一个板由以下组成 N \times N 细胞。左上角的单元格有坐标 (0, 0)和一个单元格 i 向下行并 j 右侧的列有坐标 (i, j)。的外边缘 N \times N 网格被墙包围,相邻单元之间也可能有墙。
每个单元格都可以涂上一种颜色。让 C 是使用的颜色总数,其中每种颜色由一个整数表示 0, 1, \ldots, C-1。您可以自由设置棋盘的初始颜色。
机器人有一个变量代表其 内部状态。该内部状态可以取任意值 0 to Q-1,其中 Q 是可能的状态总数,您可以自由选择。初始内部状态为 0.
基于当前颜色 细胞的 c 和内部状态 q,机器人确定下一步动作并同时执行以下三个操作:
- 用颜色重新绘制当前单元格 A(c, q) (可以用相同的颜色重新绘制)。
- 将其内部状态更新为 S(c, q) (可能会更新到相同的状态)。
- 朝以下方向移动 D(c, q) (上、下、左、右或保持原位)。如果当前单元格和目的地之间有墙,机器人将无法移动并保持在原地。
在这里, A, S,和 D 是定义 转换规则。这些转换规则必须在机器人开始运行之前设计,并且在运行过程中不能更改。此外,机器人的动作不取决于其当前位置,仅取决于当前单元格的颜色和内部状态。
机器人操作示例
在上面的示例中,机器人从 3 \times 3 板最初漆成蓝色,位于位置 (0, 0),并根据以下三个转换规则进行操作:
- A(\text{blue}, 0) = \text{green}, S(\text{blue}, 0) = 0, D(\text{blue}, 0) = \text{right}
- A(\text{green}, 0) = \text{blue}, S(\text{green}, 0) = 1, D(\text{green}, 0) = \text{left}
- A(\text{green}, 1) = \text{green}, S(\text{green}, 1) = 1, D(\text{green}, 1) = \text{down}
在前三个步骤中,重复应用转换规则 1,将单元格重新绘制为绿色并向右移动。第三步,机器人撞到墙壁而无法移动,因此它停留在原地。 第四步,由于当前单元格为绿色,因此应用转换规则 2,将其重新绘制为蓝色,向左移动,并将内部状态更改为 1。 最后,在第五步中,由于当前单元格为绿色且内部状态为1,因此应用转换规则3,机器人向下移动。
一系列 K 目标单元格 (x_0, y_0), (x_1, y_1), \ldots, (x_{K-1}, y_{K-1}) 和上限 T 给出了关于步骤的数量。机器人从细胞开始 (x_0, y_0) 并旨在按指定顺序访问所有目的地 T 步骤。
如果机器人到达目的地 (x_j, y_j) 在轮到之前(即,在到达所有之前的目的地之前) (x_i, y_i) 为 i < j),该访问不算数。机器人必须到达 一旦成为当前目的地,请再次 (x_j, y_j) 。
设计棋盘的初始颜色配置和机器人的转换规则,以便按顺序访问所有目的地。
评分
让 C 是使用的颜色数量, Q 是使用的状态数,并且 V 是步数限制内按顺序成功访问的目的地数量 T。然后,绝对分数计算如下:
- If V = K: C + Q
- If V < K: 2N^4 + (K - V) \times N^2
绝对分数越低越好。
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。
最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅针对 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
- 系统测试:2000年。我们将发布 种子.txt (sha256=c7a6f9526da67d83d1f8fed006e1b8f5edc8e4134444cf954e400a4dcd8bd130) 比赛结束后。
关于相关评价体系
在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入
输入由标准输入按以下格式给出。
N K T
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
x_0 y_0
\vdots
x_{K-1} y_{K-1}
- N 是电路板的尺寸并且满足 10 \leq N \leq 20.
- K 是目的地数量并且满足 N \leq K \leq N^2.
- 让 X 是按顺序访问所有目的地所需的最少移动次数。步数限制 T 满足 X \leq T \leq 2X.
- 每个 v_{i,0} \cdots v_{i,N-2} 是长度为的二进制字符串 N-1。的 j- 第一个字符
上字符串的 v_{i,j} 表示是否有墙(
1)或不(0) 单元格之间 (i, j) 和细胞 (i, j+1). - 每个 h_{i,0} \cdots h_{i,N-1} 是长度为的二进制字符串 N。的 j- 第一个字符
上字符串的 h_{i,j} 表示是否有墙(
1)或不(0) 单元格之间 (i, j) 和细胞 (i+1, j). - 保证所有单元格相互可达。
- (x_k, y_k) 代表坐标 k第一个目的地并满足 0 \leq x_k, y_k \leq N-1。所有目的地都是不同的。
输出
按以下格式输出到标准输出。
C Q M
s_{0,0} \cdots s_{0,N-1}
\vdots
s_{N-1,0} \cdots s_{N-1,N-1}
c_0 q_0 A(c_0,q_0) S(c_0,q_0) D(c_0,q_0)
\vdots
c_{M-1} q_{M-1} A(c_{M-1},q_{M-1}) S(c_{M-1},q_{M-1}) D(c_{M-1},q_{M-1})
- C 是使用的颜色数量,并且必须满足 1 \le C \le N^4.
- Q 是使用的内部状态数,并且必须满足 1 \le Q \le N^4.
- M 是输出的转移规则的数量,并且必须满足 0 \le M \le T.
- s_{i,j} 是单元格的初始颜色 (i, j),并且必须满足 0 \le s_{i,j} \le C - 1.
- 每行 c_i q_i A(c_i,q_i) S(c_i,q_i) D(c_i,q_i) 表示当当前颜色为 c_i 和内部状态是 q_i:
- 0 \le c_i \le C - 1, 0 \le q_i \le Q - 1
- 同一对 (c_i, q_i) 不得出现多次。
- 重新涂色 A(c_i,q_i) 必须满足 0 \le A(c_i,q_i) \le C - 1
- 新的内部状态 S(c_i,q_i) 必须满足 0 \le S(c_i,q_i) \le Q - 1
- 移动方向 D(c_i,q_i) 必须是以下五个字符之一:
- 上:
U - 向下:
D - 左:
L - 右:
R - 留在原地:
S
- 上:
自从 C \times Q 可以非常大,没有必要输出所有的转换规则 (c, q) 对。仅输出模拟期间可能实际发生的对的规则就足够了。因为最多有 最多 T 步 T 转换规则就足够了。
但是,如果机器人遇到 (c, q) 对在执行期间没有输出转换规则,其操作在该点终止。
输入生成
让 \mathrm{rand}(L, U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
板代
我们将单元格的角点称为“顶点”。
首先,确定电路板尺寸 N = \mathrm{rand}(10, 20)。然后确定墙段的数量 W = \mathrm{rand}(0, N - 1)。从相邻单元之间不存在内墙的板开始,并重复以下过程 W 次:
随机选择一个不与任何现有墙相邻的顶点。然后选择四个方向(上、下、左、右)之一,并从该顶点沿所选方向延伸一堵墙,直到它接触另一堵墙。
目标生成
确定目的地数量 K = \mathrm{rand}(N, N^2)。随机播放 N^2 单元格均匀随机,并选择第一个 此混洗列表中的 K 单元格作为目标序列。
正在生成 T
计算最小移动次数 X 需要按顺序访问所有目的地。然后确定步数限制 T = \mathrm{rand}(X, 2X).
示例解决方案 (Python)
# Input
N, K, T = map(int, input().split())
v = [input().strip() for _ in range(N)]
h = [input().strip() for _ in range(N - 1)]
targets = [tuple(map(int, input().split())) for _ in range(K)]
# Function to check if movement is possible
DIJ = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def can_move(i, j, d):
if d == 'U':
if i == 0: return False
return h[i - 1][j] == '0'
elif d == 'D':
if i == N - 1: return False
return h[i][j] == '0'
elif d == 'L':
if j == 0: return False
return v[i][j - 1] == '0'
elif d == 'R':
if j == N - 1: return False
return v[i][j] == '0'
return False
# --- Strategy ---
# The internal state is always fixed to 0.
# Each cell is assigned a unique initial color; the color is never changed.
# The color thus represents the robot’s current position.
# The robot moves in a direction that decreases the Manhattan distance to target[1].
# If no such direction exists, it stops.
C = N * N
Q = 1
s = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
s[i][j] = i * N + j
rules = []
i, j = targets[0] # current position
gi, gj = targets[1] # first destination
for t in range(T):
d = 'S'
if i > gi and can_move(i, j, 'U'):
d = 'U'
elif i < gi and can_move(i, j, 'D'):
d = 'D'
elif j > gj and can_move(i, j, 'L'):
d = 'L'
elif j < gj and can_move(i, j, 'R'):
d = 'R'
if d == 'S':
break
rules.append((s[i][j], 0, s[i][j], 0, d))
di, dj = DIJ[d]
i, j = i + di, j + dj
# Output
print(C, Q, len(rules))
for r in range(N):
print(' '.join(map(str, s[r])))
for c, q, A, S, D in rules:
print(c, q, A, S, D)
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 1
3 3 6 00 00 00 000 000 0 0 0 2 1 1
示例输出 1
2 2 3 0 0 0 0 0 0 0 0 0 0 0 1 0 R 1 0 0 1 L 1 1 1 1 D
该输入和输出对应于问题陈述中给出的机器人操作示例。
它们仅供说明之用,不满足输入约束。
