No.253 ロウソクの長さ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 102
作問者 : krotonkroton
5 ProblemId : 687 / 出題時の順位表

問題文

ユキコちゃんとあなたはロウソクを使ったゲームをします。

ロウソクは最初 $X$ cmあります。$X$ は $10$ 以上 $10^{9}$ 以下のある整数です。
ゲーム中ユキコちゃんはロウソクを見ることができますが、あなたは見ることはできずロウソクの最初の長さも知りません。
ゲームは次の様に進行します。

  1. ユキコちゃんがロウソクに火をつけます。
  2. あなたはユキコちゃんにある非負整数 $Y$ について「現在のロウソクの長さは $Y$ cmですか?」と質問できます。
  3. ユキコちゃんは現在のロウソクの長さが $Y$ cmより「短い」か「長い」か「等しい」かをあなたに答えます。
  4. ロウソクが1cm短くなります。ただしすでに燃え尽きている場合、つまり0cmの場合は0cmのままです。
  5. あなたがまだ質問したい場合は2.に戻る。そうでないなら終了。

100回までの質問でロウソクの最初の長さ $X$ を当ててください。

入出力

あなたが提出したプログラム(以下、回答プログラムとする)は2種類のクエリを標準出力に出力しなければならない。
クエリは現在のロウソクの長さがある非負整数$Y$であるか尋ねる質問クエリと、ロウソクの最初の長さ $X$ がある非負整数 $Y$ であると回答する回答クエリである。
質問クエリのフォーマットは
"$?$ $Y$"であり、
回答クエリのフォーマットは
"$!$ $Y$"である。
質問クエリ及び回答クエリにおいて$Y$が整数ではない$Y$が負である$Y$が32bit符号付整数に収まらない範囲の場合はいずれも不正解となる。

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

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

注意点

  • ジャッジの制限時間は2秒としているが、応答プログラムの反応時間をも含めている。
  • 2種類のクエリ以外の出力を行った場合は不正解となる。
  • 標準エラー出力への出力は質問クエリとも回答クエリとも不正な出力ともみなされない。
プログラムの例
int ask(int Y){
	cout << "? " << Y << endl;
	int res;
	cin >> res;
	return res;
}
int main(){
	int res = 123;
	for(int i=0;i<100;i++){
		int Y = rand() % 10000;
		if(ask(Y) == 0){
			res = 456;
			break;
		}
	}
	cout << "! " << res << endl;
	return 0;
}
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

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