提交形式： 文本规则文件
限制： 时间步数不超过 $5N$，状态数不超过 $40$

题目描述

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

这些机器人非常有限：

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

形式化地，在每个时间步，机器人 $i$（$1\le i\le N$）处于某个状态 $S_i$。它需要选择下一时间步转移到哪个状态。该选择只能依赖于三元组：

$$S_{i-1},S_i,S_{i+1}.$$

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

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

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

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

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

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

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

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

此外，状态数量不能超过 $40$ 个，不包括 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=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，因此失败。

本地测试

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

模拟器会在给定 $N$ 下运行你的规则，直到：

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

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

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

数据范围

• $2 \le N \le 2500$；
• 时间步数不超过 $5N$；
• 状态数不超过 $40$。

子任务

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

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

评分方式

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

设使用的状态数为 $M$，不包括 X 和 Fire。

• 若 $M\le 7$，得分比例 $S=1$；
• 否则：

$$S=\left(\frac{7}{M}\right)^{0.6}.$$