No.246 質問と回答

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 238
作問者 : 紙ぺーぱー紙ぺーぱー
4 ProblemId : 551 / 出題時の順位表
問題文最終更新日: 2015-12-01 16:09:49
この問題はリアクティブ形式の問題です!通常の問題と形式が異なることに注意してください!!!

問題文

kamipeipaa君は$1$から$10^{9}$までの範囲に含まれるある整数$x$が大好きです。しかし、意地悪なのでkamipeipaa君がそれを教えてくれることはありませんでした。
その代わり「$x$がある整数$y$以上かどうか」という質問をすることが許されました。kamipeipaa君はその質問に正直に回答することを約束してくれました。
kamipeipaa君は多忙なので$100$回までしか質問に答えたくありません。$100$回までの質問でkamipeipaa君が大好きな整数を当ててください。

入出力

あなたが提出したプログラム(以下、回答プログラムとする)は2種類のクエリを標準出力に出力しなければならない。
クエリは$x$がある整数$y$以上かどうかを尋ねる質問クエリと、$x$がある整数$y$であると回答する回答クエリである。
質問クエリのフォーマットは
"$?$ $y$"であり、
回答クエリのフォーマットは
"$!$ $y$"である。

各クエリは、行末に改行してください。
質問クエリを行うと、応答プログラムから回答プログラムの標準入力に結果が返される。$x$が$y$以上ならば$1$が、そうでないならば$0$が入力される。
出力後に、出力をflushせよ。flushしなかった場合、応答プログラムが入力を処理できず制限時間を超えてしまい、その結果不正解となることがある。 また、質問クエリの実行後必ずその結果を受け取ること。応答プログラムが入力を処理できず不正解の原因となることがある。

回答クエリの実行後、プログラムをただちに終了すること。ジャッジの制限時間を超えた結果として不正解となることがある。 この問題はスペシャルジャッジである。ジャッジの制限時間以内に終了し、質問回数が$100$回以内であり、回答クエリが出力した値$y$と$x$が一致していた場合正解とみなされる。

注意点

  • 質問クエリ及び回答クエリにおいて$y$が$64$bit符号付整数に収まらない範囲の場合の結果は不定である。
  • ジャッジの制限時間は$2$秒としているが、応答プログラムの反応時間をも含めている。
  • 2種類のクエリ以外の出力を行った場合は不正解となる。
  • 標準エラー出力への出力は質問クエリとも回答クエリとも不正な出力ともみなされない。
プログラムの例
import sys
iter = 1
res = 1
while iter <= 4:
    print ("? %d" % iter)
    sys.stdout.flush()
    res = int(input())
    iter += 1
if res==1:
    print("! %d" % res)
else:
    print("! %d" % 2)
sys.stdout.flush()

サンプル

サンプル1
回答プログラムの出力
? 1
? 2
? 3
? 4
! 2
応答プログラムの出力
1
1
0
0

1行目において回答プログラムは質問クエリを出力し、1以上であると応答プログラムは出力した。
2行目において回答プログラムは質問クエリを出力し、2以上であると応答プログラムは出力した。
3行目において回答プログラムは質問クエリを出力し、3以上でないと応答プログラムは出力した。
4行目において回答プログラムは質問クエリを出力し、4以上でないと応答プログラムは出力した。
5行目において回答プログラムは回答クエリを出力し$x$は2であると答えた。
2以上であって3以上でない整数は2以外にはないため、正解である。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。