这是一个交互问题。
Vasya 和 Petya 将玩以下游戏:Petya 有一些正整数 $$$a$$$。之后,Vasya 应该使用以下问题来猜测这个数字。他可以说出一对非负整数$$$(x, y)$$$。彼佳会回答他:
- “x”,如果 $$$(x \bmod a) \geq (y \bmod a)$$$。
- “y”,如果 $$$(x \bmod a) < (y \bmod a)$$$。
我们将 $$$(x \bmod a)$$$ 定义为 $$$x$$$ 除以 $$$a$$$ 的余数。
Vasya 应该使用不超过 60 个问题来猜出数字 $$$a$$$。
保证 Petya 有一个数,满足不等式 $$$1 \leq a \leq 10^9$$$。
帮助 Vasya 玩这个游戏并编写一个程序,该程序将猜测数字 $$$a$$$。
互动
你的程序应该玩几个游戏。
在任何游戏开始之前,您的程序应该读取以下字符串:
- “开始”(不带引号)— 新游戏的开始。
- “错误”(不带引号)— 在上一场游戏中,您找到了错误的答案。您的程序应该在读取此字符串后终止,并且它将得到“错误答案”的结论。
- “结束”(不带引号)— 所有游戏均已结束。您的程序应该在读取该字符串后终止。
读取字符串“start”(不带引号)后,新游戏开始。
首先,你的程序应该询问几个关于非负整数对 $$$(x, y)$$$ 的问题。您只能询问满足不等式 $$$0 \leq x, y \leq 2 \cdot 10^9$$$ 的数字。要提出问题,请打印“? x y”(不带引号)。作为答案,您应该阅读一个符号:
- "x"(不带引号),如果 $$$(x \bmod a) \geq (y \bmod a)$$$。
- "y"(不带引号),如果 $$$(x \bmod a) < (y \bmod a)$$$。
- “e”(不带引号)— 您提出了超过 $$$60$$$ 问题。您的程序应该在读取此字符串后终止,并且它将得到“错误答案”的结论。
在你的程序问了几个问题之后,你的程序应该以“!a”(不带引号)的形式打印答案。您应该打印满足不等式 $$$1 \leq a \leq 10^9$$$ 的数字 $$$a$$$。可以保证 Petya 的号码 $$$a$$$ 满足这个条件。之后,当前游戏将结束。
我们记得您的程序在一场游戏中不能提出超过 $$$60$$$ 的问题。
如果你的程序在读取“错误”(不带引号)、“结束”(不带引号)或“e”(不带引号)后没有终止,它可以获得任何结论,因为它将继续从关闭的输入中读取。此外,如果您的程序以不正确的格式打印答案或问题,它也可能会得到任何结论。当心。
打印问题和答案后不要忘记刷新输出。
要刷新输出,您可以使用:
- C++ 中的 fflush(stdout)。
- Java 中的 System.out.flush() 。
- Python 中的 stdout.flush() 。
- 以帕斯卡为单位的刷新(输出)。
- 请参阅其他语言的文档。
保证您玩至少 $$$1$$$ 且不超过 $$$100$$$ 游戏。
黑客:
在 hacks 中,您只能使用一款游戏。要使用 Petya 的数字 $$$a$$$ ($$$1 \leq a \leq 10^9$$$) 破解解决方案,您应该在第一行中编写一个数字 $$$1$$$,在第二行中您应该编写一个数字 $$$a$$$。
示例
输入 #1
start x x start x x y start x x y y end
输出 #1
? 0 0 ? 10 1 ! 1 ? 0 0 ? 3 4 ? 2 5 ! 2 ? 2 4 ? 2 5 ? 3 10 ? 9 1 ! 3
注意
在第一个测试中,您应该使用 Petya 的数字 $$$1$$$、$$$2$$$ 和 $$$3$$$ 玩 $$$3$$$ 游戏。
在第一场比赛中,Petya 将对任何问题回答“x”(不带引号),因为对于任何整数 $$$x$$$,$$$(x \bmod 1) = 0$$$。
在第二个游戏中,如果你问$$$(0, 0)$$$,答案将是“x”(不带引号),因为$$$(0 \bmod 2) \geq (0 \bmod 2)$$$。但如果你问$$$(2, 5)$$$对,答案将是“y”(不带引号),因为$$$(2 \bmod 2) < (5 \bmod 2)$$$,因为$$$(2 \bmod 2) = 0$$$ 和 $$$(5 \bmod 2) = 1$$$。