E - Awkward Response 解説 /

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

配点 : 800 点

問題文

これはインタラクティブな問題です。

すぬけくんはお気に入りの正の整数 N を持っています。あなたは 「n はお気に入りの正の整数か？」と最大 64 回すぬけくんに質問することができます。 N を特定してください。

すぬけくんはひねくれ者なので「n はお気に入りの正の整数か？」と質問されたとき、n が以下の 2 つの条件のどちらかを満たすとき Yes と、それ以外のとき No と答えます。

  • n \leq N かつ str(n) \leq str(N)を満たす
  • n > N かつ str(n) > str(N) を満たす

ここで、str(x) は正の整数 x を十進表記(先頭に 0 をつけない)の文字列として表したものです。例えば str(123) = 123，str(2000) = 2000 です。 なお、この問題において文字列同士は辞書順で比較されます。例えば 11111 < 123，123456789 < 9 が成立します。

制約

  • 1 \leq N \leq 10^{9}

入出力

各質問は、標準出力に以下の形式で出力せよ：

? n

ここで n は 1 以上 10^{18} 以下の整数でなければならない。

次に、質問の答えが標準入力から以下の形式で与えられる：

ans

ここで ans は Y または N である．Y ならば、質問の答えが Yes であることを、N ならば No であることを示す。

最後に、答えを以下の形式で出力せよ：

! n

ここで n=N でなくてはならない。

ジャッジ

  • 出力のあと、標準出力を flush せよ。従わない場合 TLE の可能性がある。
  • 答えを出力した後、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は定義されていない。
  • 出力の答えが間違っている場合の挙動は定義されていない(WA とは限らない)。

入出力例

これは N=123 のときの入出力例です。

Input Output
? 1
Y
? 32
N
? 1010
N
? 999
Y
! 123
  • 1 \leq 123 かつ str(1) \leq str(123) なので答えは Yes です
  • 32 \leq 123 ですが、str(32) > str(123) なので答えは No です
  • 1010 > 123 ですが、str(1010) \leq str(123) なので答えは No です
  • 999 \geq 123 かつ str(999) > str(123) なので答えは Yes です
  • N は 123 であると 4 回の質問で回答できたため正解となります

Score : 800 points

Problem Statement

This is an interactive task.

Snuke has a favorite positive integer, N. You can ask him the following type of question at most 64 times: "Is n your favorite integer?" Identify N.

Snuke is twisted, and when asked "Is n your favorite integer?", he answers "Yes" if one of the two conditions below is satisfied, and answers "No" otherwise:

  • Both n \leq N and str(n) \leq str(N) hold.
  • Both n > N and str(n) > str(N) hold.

Here, str(x) is the decimal representation of x (without leading zeros) as a string. For example, str(123) = 123 and str(2000) = 2000. Strings are compared lexicographically. For example, 11111 < 123 and 123456789 < 9.

Constraints

  • 1 \leq N \leq 10^{9}

Input and Output

Write your question to Standard Output in the following format:

? n

Here, n must be an integer between 1 and 10^{18} (inclusive).

Then, the response to the question shall be given from Standard Input in the following format:

ans

Here, ans is either Y or N. Y represents "Yes"; N represents "No".

Finally, write your answer in the following format:

! n

Here, n=N must hold.

Judging

  • After each output, you must flush Standard Output. Otherwise you may get TLE.
  • After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Sample

Below is a sample communication for the case N=123:

Input Output
? 1
Y
? 32
N
? 1010
N
? 999
Y
! 123
  • Since 1 \leq 123 and str(1) \leq str(123), the first response is "Yes".
  • Since 32 \leq 123 but str(32) > str(123), the second response is "No".
  • Since 1010 > 123 but str(1010) \leq str(123), the third response is "No".
  • Since 999 \geq 123 and str(999) > str(123), the fourth response is "Yes".
  • The program successfully identifies N=123 in four questions, and thus passes the case.