[IATI2017 day1]robots(提交答案题)
题目描述
有两个小机器人正在一条只由字符 A 和 B 组成的字符串上爬行。它们的目标是判断这个字符串是 fine 还是 coarse。
如果字符串的中间三分之一中 A 的个数与 B 的个数相等，那么这两个机器人认为该字符串是 fine；否则认为该字符串是 coarse。
例如：
- 字符串
BBABAABBBABA是 fine，因为它的中间三分之一是AABB，其中有两个A和两个B； - 字符串
BAABABBBBAAB是 coarse，因为它的中间三分之一是ABBB，其中有一个A和三个B； - 字符串
AABBAABB同样是 coarse，因为它没有中间三分之一。
在任意时刻，每个机器人都占据字符串上的一个字符位置，并且它能够感知以下信息：
- 它当前站在的是：
- 最左端字符；
- 中间字符；
- 最右端字符。
- 当前这个位置上是只有它自己，还是两个机器人都在同一位置。
- 它脚下的字符是
A还是B。
除此之外，每个机器人还能够记住自己行走过程中的一些信息，但不幸的是，每个机器人的记忆只有 4 个比特。
每个机器人脑中都有一份“指令列表”，并且两个机器人的指令列表可以完全不同。
每条指令由三部分组成：
左侧（条件） -> （特殊字符）右侧（动作指令）
左侧条件包含
- 一个字符，表示机器人是否在字符串边界：
L：位于最左端字符；I：位于内部字符；R：位于最右端字符。
- 一个字符，表示当前位置有几个机器人：
O：当前位置只有一个机器人；T：当前位置有两个机器人。
- 当前脚下字符：
A或B。
- 4 个字符，每个是
0或1，表示该机器人的记忆内容，例如0101表示其记忆当前为0101。
因此，左侧整体构成了一个合取条件，其真假由机器人当前所处位置和 4 比特记忆共同决定。
右侧动作包含
- 一个字符，表示机器人接下来要执行的动作：
L：向左移动一格；R：向右移动一格；S：停在原地；Y：报告字符串是 fine；N：报告字符串是 coarse。
- 如果动作不是
Y或N，则后面还跟着 4 个字符（0或1），表示更新后的记忆内容，例如0110。
通配符 ?
除两个特殊字符和动作字符之外，指令中的任意字符都可以替换为通配符 ?。
- 若
?出现在左侧条件中，表示对应条件不进行检查； - 若
?出现在动作后面的记忆覆盖部分中，表示对应比特保持不变。
例如，下面这条指令：
LT???01->R??10
含义是：
如果机器人位于最左端字符、另一个机器人与它处于同一位置，并且它记忆的最后两位是 0 和 1，那么（不管它当前站在 A 还是 B 上）它都要向右移动一步，并将记忆的最后两位改成 1 和 0，前两位保持不变。
两个机器人开始时都位于字符串的最左端字符上，且它们的 4 位记忆初始全为 0。
每毫秒，每个机器人都会：
- 观察周围环境；
- 查看自己的记忆；
- 在指令列表中寻找可执行的规则；
- 决定向左一步、向右一步、原地不动，或者直接给出它对字符串的判断；
- 并且可以把新的信息记到记忆里。
只要任意一个机器人给出了判断，它们的任务就结束，并全部关闭。如果两个机器人恰好同时给出判断，则以前一个机器人的判断为准。
更具体地说，每个机器人会按顺序检查自己的指令列表，寻找与当前状态完全匹配的第一条指令；若找到，就执行它。否则，它会重新从头扫描整张列表，并执行第一条带有通配符、且与当前位置及记忆相符的指令。若仍然找不到匹配项，则两个机器人会直接关闭，且未能完成任务。
你的任务是为这两个机器人分别设计一份指令列表，使得它们对于任意一个长度至少为两个字符、且只由 A 和 B 组成的字符串，都能始终正确判断它是 fine 还是 coarse。
任务类型
这是一道输出文件题。
你需要创建并提交一个名为 robots.txt 的文本文件，其内容顺序如下：
- 一行文字
Robot 1 - 若干行第一台机器人的指令（每行一条）
- 一行文字
Robot 2 - 若干行第二台机器人的指令（每行一条）
文件 robots.txt 中也可以包含注释行。注释行以字符 % 开头，这类行会被机器人直接跳过。
数据范围与要求
- 两个机器人在宣布字符串类别之前，总步数不能超过字符串长度的
1000倍。 - 每个测试包含
16或20个字符串。 - 每个字符串长度至少为
12，至多为3600。 - 字符串中的每个字符都是
A或B。 - 有一个测试只包含长度为
12的字符串。 - 另有两个测试只包含长度不超过
36的字符串。
评分方式
对于每个测试，只要两个机器人能在不超过字符串长度 1000 倍的步数内，对其中所有字符串都作出正确判断，则该测试得满分；否则该测试得 0 分。
样例
为了便于说明，我们考虑一个远比原题简单得多的任务：
机器人把“长度为 3 且第三个字符是 A 的字符串”视为 fine。也就是说，只有 AAA、ABA、BAA 和 BBA 被认为是 fine。
这个任务可以用非常简单的策略完成。事实上，只需要一个机器人工作即可，另一个保持不动。“工作的那个”机器人只需向右走两步，然后检查自己是否到达了最右端，且当前字符是否为 A。
robots.txt
Robot 1
???????->S????
Robot 2
L??0000->R0001
I??0001->R0010
R??0001->N
R?A0010->Y
R?B0010->N
I??0010->N
样例解释
robots.txt 中的内容 |
说明 |
|---|---|
Robot 1 |
对于机器人 1 |
???????->S???? |
无论处于什么状态，都原地不动 |
Robot 2 |
对于机器人 2 |
L??0000->R0001 |
若位于最左端且记忆为 0000，则向右走，并把记忆改成 0001 |
I??0001->R0010 |
若位于中间位置且记忆为 0001，则向右走，并记住 0010 |
R??0001->N |
若位于最右端且记忆为 0001，说明字符串长度只有 2，因此判定为 coarse |
R?A0010->Y |
若位于最右端、当前字符为 A 且记忆为 0010，则判定为 fine |
R?B0010->N |
若位于最右端、当前字符为 B 且记忆为 0010，则判定为 coarse |
I??0010->N |
若还没有到达最右端，则说明字符串过长，判定为 coarse |
本地测试解释器
题目提供了一个解释器 robots.cpp 供本地测试使用。
请将它放在你编写 robots.txt 的同一目录中。你可以用它来对自己输入的字符串进行测试。如果编译后的可执行文件与 robots.txt 位于同一目录中，它也可以在控制台模式下运行。
解释器还支持跟踪模式（trace mode）：程序会一步一步执行任务，显示机器人的状态，并在每一步等待你从标准输入按回车继续。
运行方式
若不带参数运行，解释器会从标准输入读取一个字符串，并在不跟踪的情况下执行 robots.txt 中的指令。
若带一个参数：
- 如果该参数是一个合法的只由
A和B组成的字符串，则检查该字符串，且不跟踪； - 如果该参数不是合法字符串，则解释器会改为从标准输入读取字符串，并打开跟踪模式。
若带两个参数，则第一个参数被视为待检查字符串，第二个参数的存在会打开跟踪模式。
例如：
robots ABAB
检查字符串ABAB，不跟踪；robots ABAB 1
检查字符串ABAB，并跟踪执行过程；robots 1
从控制台读取字符串，并在跟踪模式下执行。
当然，你也可以按自己的需要修改这个解释器。