CF1103B Game with modulo

这是一个交互题。 Vasya 和 Petya 要玩如下的游戏：Petya 拥有一个正整数 $a$。之后 Vasya 需要通过提问来猜出这个数。每次他可以提出一对非负整数 $(x, y)$，Petya 会回答： - 如果 $x \bmod a \geq y \bmod a$，则回答 "x"。 - 如果 $x \bmod a < y \bmod a$，则回答 "y"。 这里 $(x \bmod a)$ 表示 $x$ 除以 $a$ 的余数。 Vasya 需要在不超过 $60$ 次提问内猜出 $a$。 保证 Petya 的数 $a$ 满足 $1 \leq a \leq 10^9$。 请帮助 Vasya 玩这个游戏，并编写一个程序来猜出 $a$。

你的程序需要进行多轮游戏。 在每轮游戏开始前，你的程序应读取如下字符串之一： - "start"（不带引号）——表示新一轮游戏开始。 - "mistake"（不带引号）——上一轮游戏你猜错了答案。读取到该字符串后你的程序应立即终止，否则会被判为“Wrong answer”。 - "end"（不带引号）——所有游戏结束。读取到该字符串后你的程序应立即终止。 读取到 "start" 后，进入新一轮游戏。 在游戏过程中，你可以多次询问一对非负整数 $(x, y)$，要求 $0 \leq x, y \leq 2 \times 10^9$。每次提问请输出 "? x y"（不带引号）。Petya 会回复： - "x"（不带引号），如果 $x \bmod a \geq y \bmod a$。 - "y"（不带引号），如果 $x \bmod a < y \bmod a$。 - "e"（不带引号），如果你提问次数超过 $60$ 次。读取到该字符串后你的程序应立即终止，否则会被判为“Wrong answer”。 在提问若干次后，你需要输出答案，格式为 "! a"（不带引号），其中 $a$ 满足 $1 \leq a \leq 10^9$。保证 Petya 的数 $a$ 满足该条件。之后本轮游戏结束。 注意：每轮游戏最多只能提问 $60$ 次。 如果你的程序在读取到 "mistake"、"end" 或 "e" 后没有终止，可能会被判为任意结果，因为会继续读取已关闭的输入。如果你的程序输出的答案或提问格式不正确，也可能被判为任意结果，请务必小心。 输出后请务必刷新输出缓冲区。 刷新输出的方法如下： - C++：fflush(stdout) - Java：System.out.flush() - Python：stdout.flush() - Pascal：flush(output) - 其它语言请参考相关文档。 保证你需要进行至少 $1$ 轮、至多 $100$ 轮游戏。 Hack 数据说明： 在 hack 数据中，只会进行一轮游戏。要 hack 某个 Petya 的数 $a$（$1 \leq a \leq 10^9$），请在第一行写一个数 $1$，第二行写 $a$。

（同上，见输入格式）

在第一个测试点中，你需要和 Petya 玩 $3$ 轮，Petya 的数分别为 $1$、$2$ 和 $3$。 在第一轮中，Petya 会对任何提问都回答 "x"，因为 $x \bmod 1 = 0$ 对任意整数 $x$ 都成立。 在第二轮中，如果你提问 $(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$。 由 ChatGPT 4.1 翻译