P13612 [IOI 2018] combo 组合动作

你在玩一个动作游戏。游戏控制器有 $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$。 ### 实现细节 ~~你的程序需要引入头文件 `combo.h`。~~ 你无需引入头文件 `combo.h`。但是，你需要在你的程序开头加上： ```cpp int press(string p) ``` 此外，建议以 C++20 或者 C++23 提交本题（而非 C++14/GCC9）。 你需要实现下面的函数： ```cpp string guess_sequence(int N) ``` * `N`：串 $S$ 的长度。 * 对每个测试用例，该函数被调用恰好一次。 * 该函数应返回串 $S$。 你的程序可以调用下面的函数： ```cpp int press(string p) ``` * `p`：你的按键序列。 * `p` 必须是长度为从 $0$ 到 $4N$ 的串（包括 $0$ 和 $4N$）。`p` 的每个字符必须是 `A`、`B`、`X` 或者 `Y`。 * 对每个测试用例，你调用该函数的次数不能超过 $8\ 000$ 次。 * 该函数的返回结果是，当按出按键序列 `p` 后你赚到的金币数量。 如果不满足上面的条件，你的程序将被判为 `Wrong Answer`。否则，你的程序将被判为 `Accepted`，而你的得分将根据 `press` 的调用次数来计算（参见子任务）。

评测程序示例将读取如下格式的输入： * 第 $1$ 行：$S$ 如果你的程序被判为 `Accepted`，评测系统示例将打印出 `Accepted: q`，这里 `q` 为函数 `press` 的调用次数。 如果你的程序被判为 `Wrong Answer`，它打印出 `Wrong Answer: MSG`。各类 `MSG` 的含义如下： * `invalid press`：输入到 `press` 的值 `p` 是无效的。也就是说，`p` 的长度不在 $0$ 到 $4N$ 之间（含 $0$ 和 $4N$），或者 `p` 的某些字符不是 `A`、`B`、`X` 和 `Y`。 * `too many moves`：函数 `press` 的调用次数超过 $8\ 000$ 次。 * `wrong guess`：`guess_sequence` 返回的不是 $S$。

无

### 限制条件 * $1\le N\le 2\ 000$ * 串 $S$ 的每个字符必须是 `A`、`B`、`X` 或 `Y`。 * $S$ 的首字符不会再 $S$ 中重复出现。 在本题中，评测程序**不是**适应性的。意思是说，在评测程序开始运行的时候 $S$ 就固定下来，而且不依赖于你的程序所做的询问。 ### 子任务 1. （5分）$N=3$ 2. （95分）没有附加限制。对该子任务，你在每个测试用例上的得分将计算如下。设 $q$ 为调用 `press` 的次数。 * 如果 $q\le N+2$，你的得分为 $95$。 * 如果 $N+2