#5125. 「RMI 2018」Password

题目描述

题目译自 Romanian Master of Informatics 2018 Day1 T2 「Password」

你又忘记了自己的密码！现在，你正坐在电脑前，尝试输入各种密码，只记得密码只包含小写字母。幸运的是，登录系统不仅会提示"密码错误"，还会告诉你输入的密码中最长的前缀长度，这个前缀作为密码的一个（不一定连续的）子序列出现。形式上，对于密码 $P = p_1 p_2 \ldots p_N$ 和输入 $Q = q_1 q_2 \ldots q_N$，系统返回最大的 $L$，满足存在编号 $1 \leq k_1 < k_2 < \cdots < k_L \leq N$，使得对于所有 $1 \leq i \leq L$，$q_i = p_{k_i}$。系统还会告诉你 $N$（密码长度）和 $S$（密码仅使用字母表的前 $S$ 个字母）。例如，$S = 4$ 意味着密码只包含 a、b、c 和 d（但不一定全包含）。

请帮助你找回密码！

---

实现细节

这是一个交互题。你需要实现以下函数：

C：

char* guess(int n, int s);

C++：

string guess(int n, int s);

参数：$N$ 和 $S$，如上所述。 返回值：正确的密码。

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

C：

int query(char* str);

C++：

int query(string str);

参数：一个长度为 $1$ 到 $N$ 的字符串，包含字母表前 $S$ 个字母中的字符。 返回值：一个介于 $0$ 和字符串长度之间的整数，表示登录系统对你的查询的回答。

为避免编译错误，你应在全局作用域内使用上述确切声明，在调用前定义。 每个测试点最多调用该函数 $50000$ 次。 你的程序可以定义其他辅助函数。

---

示例评分程序

我们提供了示例评分程序 grader.{c,cpp}，供你在本地测试代码。评分程序从文件 password.in 读取输入，格式如下：

• 第 $1$ 行：$N$ $S$
• 第 $2$ 行：密码

你可以将评分程序与你的代码一起编译，然后运行生成的可执行文件，以测试你的猜测策略对给定输入的表现。

---

样例

假设密码为 aab。评分程序调用 guess(3, 2)。调用日志可能如下：

调用	返回值
query("ab")	$2$
query("abb")
query("bab")	$1$
query("aab")	$3$

此时，guess(3, 2) 应返回 "aab"。

---

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5000$
• $2 \leq S \leq 26$
• 每个测试点最多调用 query 函数 $50000$ 次

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	10	$N \leq S \leq 26$，密码中的所有字母互不相同
2	20	$2 \leq N \leq 100$ 且 $2 \leq S \leq 4$
3		$2 \leq N \leq 2000$ 且 $2 \leq S \leq 20$
4	30	$2 \leq N \leq 3500$
5	20	$2 \leq N \leq 5000$

---