AT_agc044_d [AGC044D] Guess the Password
题目描述
[problemUrl]: https://atcoder.jp/contests/agc044/tasks/agc044_d
**这是一个交互式问题。**
你的任务是猜出一个秘密密码 $S$。密码是一个长度不超过 $L$ 的非空字符串，且密码的每个字符都是小写英文字母（a, b, ..., z）、大写英文字母（A, B, ..., Z）或数字（0, 1, ..., 9）中的一个。
你可以通过发送查询来猜测秘密密码 $S$。每次查询，你需要发送一个满足上述密码要求的字符串 $T$，对于每个查询，你将获得 $S$ 和 $T$ 的编辑距离（允许的操作为删除、插入、替换）的结果作为反馈。你最多可以发送 $Q$ 次查询。
**注意：** 编辑距离（允许的操作为删除、插入、替换）的定义可参考 [Wikipedia 上的此页面](https://en.wikipedia.org/w/index.php?title=Levenshtein_distance&oldid=954598393)。
输入格式
要发送查询，请向标准输出输出如下格式（末尾需换行）：
> ? $T$
其中，字符串 $T$ 必须满足密码的要求。
对于每个查询的回复 $ans$，会从标准输入以如下格式给出：
> $ans$
当你确定了秘密密码 $S$ 后，请向标准输出输出如下格式（末尾需换行）：
> ! $S$
然后立即终止程序。
输出格式
见上文。
说明/提示
### 限制
- $L = 128$
- $Q = 850$
- 秘密密码 $S$ 在程序与评测机交互开始前已被选定。
### 判定
- **每次输出后必须刷新标准输出。** 如果不这样做，评测结果可能会是 `TLE`。
- 输出你认为的秘密密码后，必须立即终止程序。否则评测结果未定义。
- 如果发送了格式不正确的查询（例如，发送的字符串不满足密码要求，输出行首不是 `?`），程序异常终止，或查询次数超过 $Q$，评测结果未定义（不一定是 `WA`）。
### 输入输出样例
在以下示例中，秘密密码为 `Atcod3rIsGreat`。
| 输入 | 输出 |
| :--- | :--- |
| $?\ AtcoderIsBad$ | $5$ |
| $?\ AtcoderIsGreat$ | $1$ |
| $!\ Atcod3rIsGreat$ | |
由 ChatGPT 4.1 翻译