U114088 [IOI 2018] Combo

IOI 2018 Day 1 Task 1 **这是一道交互题，仅支持 C++ 语言。** 由于原题数据过多，故自造随机数据 (如果你会这题，就会知道强度可以保证)。 [generator](https://www.luogu.com.cn/paste/t33qqfls) 注：洛谷上并不使用该交互库，因此你的程序不应依赖该交互库。

你在玩一个动作游戏。游戏控制器有 $4$ 个按键，A、B、X 和 Y。在游戏中，你用组合动作来赚金币。你可以依次按这些按键来完成一个组合动作。 这个游戏有一个隐藏的按键序列，可以表示为由这 $4$ 个字符组成的串 $S$。你并不知道这个串 $S$ ，但是你知道它的长度为 $N$。 **你还知道，$S$ 的首字符不会在串中重复出现。** 例如，$S$ 可以是 “ABXYY” 或者 “XYYAA”，但不能是 “AAAAA” 或 “BXYBX”。 你可以依次按最多 $4N$ 个按键来完成一个组合动作。串 $p$ 为你所按的按键序列。你用这个组合动作赚到的金币数量，等于同时为 $p$ 之子串和 $S$ 之前缀的最长字符串的长度。串 $t$ 的子串定义为 $t$ 中的连续字符序列 (可以为空)。$t$ 的前缀定义为 $t$ 的子串，其或者为空，或者包含 $t$ 的首字符。 例如，如果 $S$ 是 “ABXYY”，而 $p$ 是 “XXYYABYABXAY”，你会得到 $3$ 个金币，因为 “ABX” 是可作为 $p$ 的子串的 $S$ 的前缀中最长的。 你的任务是，用少量的组合动作，找出隐藏字符串 $S$。 ### 实现细节 你需要实现下面的函数： ```cpp std::string guess_sequence(int N) ``` - $N$：串 $S$ 的长度。 - 对每个测试用例，该函数被调用恰好一次。 - 该函数应返回串 $S$。 你的程序可以调用下面的函数： ```cpp int press(string p) ``` - $p$：你的按键序列。 - $p$ 必须是长度为从 $0$ 到 $4N$ 的串 (包括 $0$ 和 $4N $)。$p$ 的每个字符必须是 A、B、X 或者 Y。 - 对每个测试用例，你调用该函数的次数不能超过 $8000$ 次。 - 该函数的返回结果是，当按出按键序列 $p$ 后你赚到的金币数量。 如果不满足上面的条件，你的程序将被判为 Wrong Answer。否则，你的程序将被判为 Accepted，而你的得分将根据 `press` 的调用次数来计算 (参见子任务)。 注：在洛谷上，你不需要 `#include "combo.h"`，但需要完成： ```cpp // headers extern "C" int press(std::string p); // 需要声明这个函数 extern "C" std::string guess_sequence(int N) ```

无

无

### 例子 设 $S$ 为 “ABXYY”。评测程序调用了 `guess_sequence(5)`。数据交互过程的例子如下所示： | 调用 | 返回值 | | ----------------------- | ------ | | `press("XXYYABYABXAY")` | $3$ | | `press("ABXYY")` | $5$ | | `press("ABXYYABXYY")` | $5$ | | `press("")` | $0$ | | `press("X")` | $0$ | | `press("BXYY")` | $0$ | | `press("YYXBA")` | $1$ | | `press("AY")` | $1$ | 对于 `press` 的第 $1$ 次调用，”ABX” 是 “XXYYABYABXAY” 的子串，而 “ABXY” 不是，因此返回 $3$。 对于 `press` 的第 $3$ 次调用，”ABXYY” 本身是 “ABXYYABXYY” 的子串，因此返回 $5$。 对于 `press` 的第 $6$ 次调用，除了空串以外没有 “ABXYY” 的其他前缀可以是 “BXYY” 的子串，因此返回 $0$。 最后，`guess_sequence(5)` 应当返回 “ABXYY”。 附件压缩包中的文件 `sample-01-in.txt` 对应于本例。 ### 限制条件 - $1 \le N \le 2000$ - 串 $S$ 的每个字符必须是 A、B、X 或 Y。 - $S$ 的首字符不会在 $S$ 中重复出现。 在本题中，评测程序 **不是** 适应性的。意思是说，在评测程序开始运行的时候 $S$ 就固定下来，而且不依赖于你的程序所做的询问。 ### 子任务 1. ($5$ 分) $N = 3$ 2. ($95$ 分) 没有附加限制。 对该子任务，你在每个测试用例上的得分将计算如下： 设 $q$ 为调用 `press` 的次数。 - 如果 $q \le N + 2$，你的得分为 $95$。 - 如果 $N + 2 < q \le N + 10$，你的得分为 $95 - 3(q - N - 2)$。 - 如果 $N + 10 < q \le 2N + 1$，你的得分为 $25$。 - 如果 $\max(N + 10, 2N + 1) < q \le 4N$，你的得分为 $5$。 - 否则，你的得分为 $0$。 注意，你在每个子任务上的得分，等于你在该子任务下所有测试用例上的最低得分。 ### 评测程序实例 评测程序示例将读取如下格式的输入： - 第 $1$ 行：$S$ 如果你的程序被判为 Accepted，评测系统示例将打印出 `Accepted: q`，这里 $q$ 为函数 `press` 的调用次数。 如果你的程序被判为 Wrong Answer，它打印出 `Wrong Answer: MSG`。各类 MSG 的含义如下： - `invalid press`：输入到 press 的值 $p$ 是无效的。也就是说，$p$ 的长度不在 $0$ 到 $4N$ 之间 (含 $0$ 和 $4 N$)，或者 $p$ 的某些字符不是 A、B、X 和 Y。 - `too many moves`：函数 `press` 的调用次数超过 $8000$ 次。 - `wrong guess`：`guess_sequence` 返回的不是 $S$。