AT_agc044_d.[AGC044D] Guess the Password

这是一个交互式问题。

你的任务是猜出一个秘密密码 $S$。密码是一个长度不超过 $L$ 的非空字符串，且密码的每个字符都是小写英文字母（a, b, ..., z）、大写英文字母（A, B, ..., Z）或数字（0, 1, ..., 9）中的一个。

你可以通过发送查询来猜测秘密密码 $S$。每次查询，你需要发送一个满足上述密码要求的字符串 $T$，对于每个查询，你将获得 $S$ 和 $T$ 的编辑距离（允许的操作为删除、插入、替换）的结果作为反馈。你最多可以发送 $Q$ 次查询。

注意： 编辑距离（允许的操作为删除、插入、替换）的定义可参考 Wikipedia 上的此页面。

要发送查询，请向标准输出输出如下格式（末尾需换行）：

? $T$

其中，字符串 $T$ 必须满足密码的要求。

对于每个查询的回复 $ans$，会从标准输入以如下格式给出：

$ans$

当你确定了秘密密码 $S$ 后，请向标准输出输出如下格式（末尾需换行）：

! $S$

然后立即终止程序。

见上文。

限制

• $L = 128$
• $Q = 850$
• 秘密密码 $S$ 在程序与评测机交互开始前已被选定。

判定

• 每次输出后必须刷新标准输出。 如果不这样做，评测结果可能会是 TLE。
• 输出你认为的秘密密码后，必须立即终止程序。否则评测结果未定义。
• 如果发送了格式不正确的查询（例如，发送的字符串不满足密码要求，输出行首不是 ?），程序异常终止，或查询次数超过 $Q$，评测结果未定义（不一定是 WA）。

输入输出样例

在以下示例中，秘密密码为 Atcod3rIsGreat。

输入	输出
$?\ AtcoderIsBad$	$5$
$?\ AtcoderIsGreat$	$1$
$!\ Atcod3rIsGreat$

由 ChatGPT 4.1 翻译