← 返回题目列表

Codeforces · 1482/G

G. 瓦银行

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

古斯塔是一家大型银行的首席银行经理。他可以无限制地访问银行的数据库系统,只需点击几下,他就可以将任意数量的资金从银行的储备金转移到他自己的私人账户。然而,该银行使用了一些奇特的人工智能欺诈检测系统,使盗窃变得更加困难。

Gustaw 知道反欺诈系统只会检测任何超过固定限额 $$$M$$$ 欧元的操作,并且这些操作由许多职员手动检查。因此,任何超过此限制的欺诈操作都会被检测到,而任何较小的操作都不会被注意到。

Gustaw 不知道 $$$M$$$ 的极限,并且想找出它。在一次操作中,他可以选择某个整数 $$$X$$$ 并尝试将 $$$X$$$ 欧元从银行的储备金转移到他自己的帐户中。然后,会发生以下情况。

- 如果 $$$X \le M$$$,则该操作不会被注意到,并且 Gustaw 的帐户余额会增加 $$$X$$$ 欧元。
- 否则,如果 $$$X > M$$$,则检测到欺诈并取消。此外,古斯塔还必须从自己的账户中支付$$$X$$$欧元作为罚款。如果他的账户上的金额少于 $$$X$$$ 欧元,他将被解雇并被带到警察局。

最初 Gustaw 的账户上有 $$$1$$$ 欧元。帮助他在不超过 $$$105$$$ 的操作中找到 $$$M$$$ 的确切价值,而不会让他被解雇。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。

对于每个测试用例,在第一次查询之前没有输入,但您可以确定 $$$M$$$ 是整数,并且 $$$0 \le M \le 10^{14}$$$。

互动

当您想要进行操作时,打印一行,格式为“? $$$X$$$”,表示您尝试移动$$$X$$$欧元($$$1 \le X \le 10^{14}$$$)。作为响应,读取可以采用以下值的单行:

- “幸运!”,如果 $$$X \le M$$$。您的余额增加 $$$X$$$。
- “欺诈者!”,如果 $$$X > M$$$。您的余额减少了 $$$X$$$。
- “被解雇!”,如果 $$$X > M$$$,但您无法支付 $$$X$$$ 欧元的罚款。在这种情况下,您的程序必须立即终止。如果超出查询数量,您也会收到此响应。

在每个测试用例中您最多可以进行 $$$105$$$ 这样的查询。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

要进行破解,请准备以下格式的输入。

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例都用包含单个整数 $$$M$$$ ($$$0 \le M \le 10^{14}$$$) 的行进行描述。

输出

对于每个测试用例,当您知道 $$$M$$$ 的确切值时,以格式“! $$$M$$$”打印一行。之后,您的程序应该继续进行下一个测试用例,或者终止(如果它是最后一个测试用例)。

示例

输入 #1

1

Lucky!

Lucky!

Lucky!

Lucky!

Lucky!

Fraudster!

输出 #1

? 1

? 2

? 3

? 4

? 5

? 6

! 5

注意

在示例中$$$M = 5$$$,因此检测到$$$X = 6$$$ 的操作。此时,Gustaw 的余额为 $$$16$$$ 欧元,因此他只需支付罚款即可。