2863 「IOI2018」组合动作

你在玩一个动作游戏。游戏控制器有 $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。

你需要实现下面的函数：

string guess_sequence(int N)

• N：串 $S$ 的长度。
• 对每个测试用例，该函数被调用恰好一次。
• 该函数应返回串 $S$。

你的程序可以调用下面的函数：

int press(string p)

• p：你的按键序列。
• p 必须是长度为从 $0$ 到 $4N$ 的串（包括 $0$ 和 $4N$）。p 的每个字符必须是 A、B、X 或者 Y。
• 对每个测试用例，你调用该函数的次数不能超过 $8\ 000$ 次。
• 该函数的返回结果是，当按出按键序列 p 后你赚到的金币数量。

如果不满足上面的条件，你的程序将被判为 Wrong Answer。否则，你的程序将被判为 Accepted，而你的得分将根据 press 的调用次数来计算（参见子任务）。

• $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<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$ 和 $4N$），或者 p 的某些字符不是 A、B、X 和 Y。
• too many moves：函数 press 的调用次数超过 $8\ 000$ 次。
• wrong guess：guess_sequence 返回的不是 $S$。