← 返回题目列表

Codeforces · 1103/B

B. 模数游戏

中文机器翻译题面 查看原题

这是一个交互问题。

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$$$。