#P15666. [Bulgarian2025训练营]Sync(提交答案题)

[Bulgarian2025训练营]Sync(提交答案题)

提交形式: 文本规则文件
限制: 时间步数不超过 5N5N,状态数不超过 4040

题目描述

有 NN 个机器人站成一行,它们希望在同一时刻发出信号。

这些机器人非常有限:

  • 每个机器人唯一能记住的是自己当前处于什么状态;
  • 每个机器人唯一能看到的是左右相邻机器人的状态;
  • 每个机器人唯一能做的是更新自己的状态;
  • 所有机器人使用同一个时钟,也就是说它们会同时更新状态。

形式化地,在每个时间步,机器人 ii(1≤i≤N1\le i\le N)处于某个状态 SiS_i。它需要选择下一时间步转移到哪个状态。该选择只能依赖于三元组:

Si−1,Si,Si+1.S_{i-1},S_i,S_{i+1}.

机器人可以保持原状态,也可以转移到任意合法状态。所有机器人共享同一套规则,因此机器人不知道自己的编号 ii。

最左端和最右端的机器人会在外侧看到一个虚构状态 X。也就是说,令 S0S_0 和 SN+1S_{N+1} 为 X。机器人不能进入状态 X。

机器人通常处于一个特殊内建状态 Wait。系统内建规则保证:如果某个机器人处于 Wait,且它左右两侧只看到 Wait 或 X,那么它会继续保持 Wait。

如果所有机器人都从 Wait 开始,将不会发生任何变化。因此在时间步 00,所有机器人都处于 Wait,但最左端机器人(机器人 11)被放入内建状态 Init。状态 Init 没有像 Wait 那样的使用限制。

之后机器人每个时间步持续更新状态,直到某个机器人进入特殊内建状态 Fire,或超过时间限制。

目标是让所有机器人在同一个时间步同时进入 Fire。

如果某一时刻只有一部分机器人进入 Fire,或者在时间限制内没有任何机器人进入 Fire,则失败。

你的任务是设计一组状态和转移规则,使得对于所有允许的 NN,机器人都能在不超过 5N5N 个时间步内同步进入 Fire。

此外,状态数量不能超过 4040 个,不包括 X 和 Fire。你还应尽量减少使用的状态数量,因为评分与状态数有关。

提交格式

你需要提交一个 .txt 文件,其中列出转移规则。

不需要显式声明状态,所有在规则中出现的状态名都会被自动视为已声明。

状态名可以是任意由非空白可打印 ASCII 字符组成的字符串,但不能包含 / 或 #。

每行至多一条规则,也允许空行。一行中 # 之后的内容视为注释,会被忽略。

规则格式为:

L M R -> E

含义是:若某机器人当前状态为 M,左邻状态为 L,右邻状态为 R,则下一时间步转移到状态 E。

为了方便书写,L、M、R 可以写成由 / 分隔的多个状态,也可以使用 ? 作为通配符,表示匹配任意可能状态。

注意:

  • L、M、R 不能是 Fire,因为一旦有机器人进入 Fire,运行就结束;
  • M 和 E 不能是 X,因为机器人不能处于 X 状态。

例如:

? A_0/Y^/10+ X -> Fire

表示最右端机器人(右邻为 X)如果处于 A_0、Y^ 或 10+ 中任一状态,则无论左邻状态是什么,都会进入 Fire。

规则优先级

如果某个机器人的情况被多条规则匹配,则使用规则文件中最靠前的一条。

例如:

Wait ? B -> Wait
? C B/Init -> A

如果实际局部状态为 Wait C B,两条规则都匹配,但由于第一条规则更靠前,中间机器人会进入 Wait。

系统内建的 Wait 规则隐式写在你的所有规则之前,因此具有更高优先级:

X/Wait Wait X/Wait -> Wait

你不需要为所有可能的三元组都定义转移规则。只有当某个未定义规则的局部状态真的出现时,才会得到 Wrong Answer。

一个失败示例

下面是一份完整但不成功的规则集,在 N=3N=3 时运行:

? Init ? -> Wait # Init always turns into a Wait
? Wait ? -> A' # Wait with a non-Wait neighbor turns into an A'

# Next are the transitions from A'
Wait A' Wait -> Wait
? A' X -> Init
Wait/X A' ? -> _B2
? A' ? -> A'

# Finally _B2 fires
X/_B2 _B2 A'/_B2 -> Fire

运行得到状态序列:

Init Wait Wait
Wait A' Wait
A' Wait A'
_B2 A' Init
Fire A' Wait

运行在某个机器人进入 Fire 时结束,但并非所有机器人同时进入 Fire,因此失败。

本地测试

提供了一个模拟器。它会读入 NN,然后一直读入你的规则直到输入结束。

模拟器会在给定 NN 下运行你的规则,直到:

  • 某个机器人进入 Fire;或
  • 超过时间步数限制。

它会输出每个时间步的状态序列,以及总时间步数和使用的状态数。

你可以任意修改模拟器代码用于调试。

数据范围

  • 2≤N≤25002 \le N \le 2500;
  • 时间步数不超过 5N5N;
  • 状态数不超过 4040。

子任务

子任务 分值 NN
1 7 ≤5\le 5
2 6 ≤15\le 15
3 14 =2K=2^K
4 =2K+1=2^K+1
5 =2K−1=2^K-1
6 =2K−2=2^K-2
7 31 无限制

只有同时通过某个子任务及其限制所包含的其他子任务,才能获得该子任务分数。

评分方式

子任务 1 和 2 没有部分分。对于其他子任务,得分比例取决于你使用的状态数量。

设使用的状态数为 MM,不包括 X 和 Fire。

  • 若 M≤7M\le 7,得分比例 S=1S=1;
  • 否则:
S=(7M)0.6.S=\left(\frac{7}{M}\right)^{0.6}.