题目描述

有一组 N 个机器人要投票决定是否接受某个提案。每个机器人投出的票要么是“是（Yes）”，要么是“否（No）”。这些机器人想知道：投“是”的机器人是否至少占了一半，从而判断提案是否通过。

虽然它们非常民主，但机器人本身能力很有限。它们站成一排，位置编号为 1 到 N。在每一个时间步开始时，第 i 个机器人处于某个状态 S_i。随后，它会“选择”自己在下一步进入什么状态（所有机器人同时进行这一更新）。

机器人没有任何记忆，而且视野也很短，因此每个机器人只能根据以下三者决定自己的下一个状态：

• 左邻居当前状态 S_{i-1}；
• 自己当前状态 S_i；
• 右邻居当前状态 S_{i+1}。

也就是说，第 i 个机器人的下一状态仅依赖于 S_{i-1}, S_i, S_{i+1}。约定边界状态 S_0 = S_{N+1} = X。另外，所有机器人都共享同一套状态转移规则。

在时间步 0 的开始时，每个机器人都处于状态 Y 或 N 之一，其中：

• Y 表示它投的是“是”；
• N 表示它投的是“否”。

之后，机器人不断按照规则更新状态，直到某个机器人宣布自己已经判断出投“是”的数量是否至少为 N/2。这通过它进入以下两个特殊状态之一来完成：

• Major：表示“至少有 N/2 个是”；
• Minor：表示“少于 N/2 个是”。

如果恰好有多个机器人在同一时间步进入这两个状态中的某一个，则以最左边那个机器人的结论为准。

你的任务是为机器人设计一套规则，使得总会有某个机器人正确判断出“是”的数量是否至少为 N/2。此外，科技部还对时间步数作了限制，因此你还希望程序尽可能快。

机器人的程序由若干行规则组成。每条规则的基本形式为：

L M R -> E

含义是：若某机器人当前状态为 M，左邻居状态为 L，右邻居状态为 R，则它下一步进入状态 E。

状态名可以是任意不含空白字符的 ASCII 字符串。

注意：

• X 表示第一个机器人左边和最后一个机器人右边的“边界状态”；
• 在 L、M、R 的位置上可以写 ?，表示任意状态；
• L、M、R 也可以写成用 / 分隔的状态列表，表示这些状态中的任意一个。

如果对某个机器人有多条规则同时匹配，则它总是使用**最靠前（最上面）**的那一条。

例如，若前三个机器人的状态为：

A 5 Back

则下面两条规则都可能适用于第二个机器人：

A ? Back -> Major
? 5 Back/A -> A

如果这两条规则都出现在你的程序中，那么该机器人会选择第一条，并宣布“是”的数量至少为 N/2。

请你完成科技部交给你的任务，编写对应的名为 robots.序号.out 的文件，并打包成zip提交。

输入文件

限制

• 1 ≤ N ≤ 1500
• 最多允许使用的时间步数：7500
• 最多允许使用的不同状态数：30

本地测试

为方便测试，你会得到一个机器人模拟器。向模拟器提供：

• N
• 机器人的投票序列
• 你的程序

之后模拟器会执行整个过程，并输出机器人的最终判断（或错误信息）。它也可以输出每一步所有机器人的状态。

解释器输入格式

第一行输入 N。
第二行输入由 N 个字符 Y 或 N 组成的字符串（表示机器人的投票）。
之后输入程序本身，格式如题目中所述。

子任务与评分

对某个子任务，你的得分取决于该子任务中所有测试点的最差结果。

如果你的程序在某个测试上：

• 非法；或
• 机器人得出了错误结论；或
• 在步数限制内没有得到任何结论；

那么该测试得分为 0。

否则，该测试得分（在 0 到 1 之间）取决于到达结论所需的时间步数 Iters：

1. 若 Iters ≤ Target，得分为 1；
2. 若 Target < Iters ≤ Target + 7，得分为 0.85；
3. 若 Target + 7 < Iters，得分为：

$$\max\left(0.75\times\left(\frac{Target+8}{Iters}\right)^{0.85},\ 0.2\right)$$

其中：

• Iters 表示到达结论所需的时间步数；
• Target 取决于子任务。

子任务如下：

子任务	分值	N ≤	Target	额外限制
1	10		N + 1	无
2	20	99		N 始终为奇数
3	30	1499	⌊N/2⌋ + 3
4	20	1500		N 始终为偶数
5				无

其中 ⌊x⌋ 表示不超过 x 的最大整数。

注意： 评测系统中的每个测试实际上还会再包含若干个子测试。你的程序会在这些子测试上分别运行，只有全部通过时，才算通过该测试。该测试的得分等于这些子测试中的最差得分。这一点不会改变题目的本质要求。