[AGC044D] Guess the Password

**本题为交互题。** 你需要猜测一个密码 $S$。密码是一个非空字符串，其长度至多为 $L$。密码中的字符可以是小写字母、大写字母和数字（a, b, ……, z, A, B, ……, Z, 0, 1, ……, 9）。 为了猜中密码，你可以进行至多 $Q$ 次询问。在一次询问中，你需要提出一个合法的密码 $T$，交互器会返回 $S$ 与 $T$ 之间的编辑距离。 对于编辑距离（编辑操作包含移除、插入和替换）的定义，可以参考[百度百科](https://baike.baidu.com/item/%E8%8E%B1%E6%96%87%E6%96%AF%E5%9D%A6%E8%B7%9D%E7%A6%BB)。 ## 交互格式 询问时，应在新的一行向标准输出打印如下内容，表示你提出的密码为 $T$： ``` ? T ``` 字符串 $T$ 必须为合法的密码。 交互器会从标准输出返回一行一个整数表示答案 $S$ 与 $T$ 之间的编辑距离。 如果已经确定了密码的内容，应在新的一行向标准输出打印如下内容，表示你的答案为 $S$： ``` ! S ``` 随后结束程序。 ## 交互机制 - 在每次打印内容后，应当刷新标准输出。反之评测结果可能为 `TLE`。 - 在输出所猜测的答案后，必须立即结束程序。其余行为均是未定义的。 - 如果所猜测的答案错误，评测结果为 `WA`。 - 如果询问格式有误（有可能提出的密码不合法，也有可能丢失了询问初始的 `?`）、你的程序意外终止或询问次数超过了 $Q$ 次，交互器的行为都是未定义的，评测结果不一定是 `WA`。 ## 数据范围 $L = 128, Q = 850$。答案 $S$ 在交互前确定。

[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) を参照してください。 ### Input & Output Format クエリを送るには、標準出力に以下のように出力せよ (末尾に改行を入れること)。 > ? $ T $ ここで、文字列 $ T $ はパスワードの要件を満たさなければならない。 クエリへの回答 $ ans $ は、標準入力から以下の形式で与えられる。 > $ ans $ 秘密のパスワード $ S $ を特定したら、標準出力に以下のように出力せよ (末尾に改行を入れること)。 > ! $ S $ そして、すぐにプログラムを終了させよ。

### 制約 - $ L\ =\ 128 $ - $ Q\ =\ 850 $ - 秘密のパスワード $ S $ は、プログラムとジャッジの対話の開始前に選ばれる。 ### 判定 - **出力のたびに標準出力を flush せよ。** これが守られない場合、ジャッジ結果が `TLE` となる可能性がある。 - 秘密のパスワード (とあなたが考えるもの) を出力したら、直ちにプログラムを終了させよ。これが守られない場合のジャッジ結果は未定義である。 - 不正な形式のクエリが送られた場合 (例: 送られた文字列がパスワードの要件を満たさない、出力の先頭に `?` がない)、プログラムが異常終了した場合、または $ Q $ 回を超えてクエリが送られた場合のジャッジ結果は未定義である (`WA` とは限らない)。 ### 入出力例 以下の例において、秘密のパスワードは `Atcod3rIsGreat` です。 Input Output $ \texttt{?\ AtcoderIsBad} $ $ 5 $ $ \texttt{?\ AtcoderIsGreat} $ $ 1 $ $ \texttt{!\ Atcod3rIsGreat} $