#P0008. 猜数字

猜数字

题目描述

这是一道交互题!

评测机会在区间 [1,109][1,10^9] 中选择一个整数,你应该写一个代码来猜测它。你最多可以问评测机 5050 个问题。

对于每一次询问,你可以向评测机询问区间 [1,109][1,10^9] 中的一个整数,评测机会返回:

  • -1,如果它小于答案。
  • 1,如果它大于或者等于答案。

每次询问,你需要先输出一个符号 ? ,表示这是一次询问,然后空格隔开后向标准输出输出一个 [1,109][1,10^9] 中的整数,表示这是你所猜测的数,然后清空缓冲区。

你可以使用如下语句来清空缓冲区:

  • 对于 C/C++:fflush(stdout);
  • 对于 C++:std::cout << std::flush;

对于 C++ 语言,在输出换行时如果你使用 std::endl 而不是 '\n',也可以自动刷新缓冲区。

然后你需要从标准输入中输入一个整数,代表评测机返回的结果。

当你已经十分确定答案是什么的时候,你应该停止询问,并输出一个字符 ! 表示接下来你准备确认答案了。接下来,空格隔开后输出一个整数,表示你所猜测的最终答案。如果你猜对了,那么你将会通过这个测试点。

样例 #1

样例输入 #1

1

1

-1

1

样例输出 #1

? 50

? 25

? 10

? 11

! 10

数据规模与约定

设 nn 为答案。

  • 对于 50%50\% 的数据,保证 n≤51n \leq 51。
  • 对于 100%100\% 的数据,保证 1≤n≤1091 \leq n \leq 10^9。