D - Guess the Password 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 1100 点

問題文

これは対話式の問題です。

あなたの課題は、秘密のパスワード S を当てることです。 パスワードは長さ L 以下の空でない文字列であり、パスワードの各文字は英小文字 (a, b, ..., z)、英大文字 (A, B, ..., Z)、数字 (0, 1, ..., 9) のいずれかです。

秘密のパスワード S を当てるために、クエリを送ることができます。 クエリは、上述のパスワードの要件を満たす文字列 T からなり、送られたクエリに対しては S と T の編集距離 (考慮する操作は文字の削除、挿入、置換) が回答されます。 送ることができるクエリの数は Q 個までです。

注記: 編集距離 (考慮する操作は文字の削除、挿入、置換) の定義については、Wikipedia 内のこちらのページ を参照してください。

制約

  • L = 128
  • Q = 850
  • 秘密のパスワード S は、プログラムとジャッジの対話の開始前に選ばれる。

入出力

クエリを送るには、標準出力に以下のように出力せよ (末尾に改行を入れること)。

? T

ここで、文字列 T はパスワードの要件を満たさなければならない。

クエリへの回答 ans は、標準入力から以下の形式で与えられる。

ans

秘密のパスワード S を特定したら、標準出力に以下のように出力せよ (末尾に改行を入れること)。

! S

そして、すぐにプログラムを終了させよ。

判定

  • 出力のたびに標準出力を flush せよ。 これが守られない場合、ジャッジ結果が TLE となる可能性がある。
  • 秘密のパスワード (とあなたが考えるもの) を出力したら、直ちにプログラムを終了させよ。これが守られない場合のジャッジ結果は未定義である。
  • 不正な形式のクエリが送られた場合 (例: 送られた文字列がパスワードの要件を満たさない、出力の先頭に ? がない)、プログラムが異常終了した場合、または Q 回を超えてクエリが送られた場合のジャッジ結果は未定義である (WA とは限らない)。

入出力例

以下の例において、秘密のパスワードは Atcod3rIsGreat です。

Input Output
\texttt{? AtcoderIsBad}
5
\texttt{? AtcoderIsGreat}
1
\texttt{! Atcod3rIsGreat}

Score : 1100 points

Problem Statement

This is an interactive task.

You have to guess a secret password S. A password is a nonempty string whose length is at most L. The characters of a password can be lowercase and uppercase english letters (a, b, ... , z, A, B, ... , Z) and digits (0, 1, ... , 9).

In order to guess the secret password S you can ask queries. A query is made of a valid password T, the answer to such query is the edit distance between S and T (the operations considered for the edit distance are: removal, insertion, substitution). You can ask at most Q queries.

Note: For a definition of edit distance (with operations: removal, insertion, substitution), see this wikipedia page.

Constraints

  • L = 128
  • Q = 850
  • The secret password S is chosen before the beginning of the interaction.

Interaction

To ask a query, print on Standard Output (with a newline at the end)

? T

The string T must be a valid password.

The answer ans to each query shall be read from Standard Input in the form:

ans

As soon as you have determined the hidden password S, you should print on Standard Output (with a newline at the end)

! S

and terminate your program.

Judgement

  • After each output, you must flush Standard Output. Otherwise you may get TLE.
  • After you print (your guess of) the hidden password, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • If the password you have determined is wrong, you will get WA.
  • If you ask a malformed query (for example because the string is not a valid password, or you forget to put ?) or if your program crashes or if you ask more than Q queries, the behavior of the judge is undefined (it does not necessarily give WA).

Samples

In the only sample testcase of this problem the hidden password is Atcod3rIsGreat.

The following one is an example of interaction if S=Atcod3rIsGreat.

Input Output
\texttt{? AtcoderIsBad}
5
\texttt{? AtcoderIsGreat}
1
\texttt{! Atcod3rIsGreat}