

Time Limit: 2 sec / Memory Limit: 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.