CF1483E Vabank

Gustaw 是一家大型银行的首席银行经理。他拥有对银行数据库系统的无限制访问权限，只需点击几下就能将任意金额从银行储备转移到自己的私人账户。然而，银行采用了一套先进的 AI 反欺诈检测系统，使得盗窃变得更加困难。 Gustaw 知道，反欺诈系统会检测任何超过某个固定限额 $M$ 欧元的操作，这些操作会被多名职员人工审核。因此，任何超过该限额的欺诈操作都会被检测到，而任何小于等于该限额的操作则不会被注意到。 Gustaw 并不知道这个限额 $M$，他想要找出这个值。在一次操作中，他可以选择某个整数 $X$，尝试将 $X$ 欧元从银行储备转入自己的账户。然后会发生以下情况： - 如果 $X \le M$，该操作不会被注意到，Gustaw 的账户余额增加 $X$ 欧元。 - 否则，如果 $X > M$，欺诈行为被检测并取消。此外，Gustaw 还必须从自己的账户中支付 $X$ 欧元作为罚款。如果他账户中的余额少于 $X$ 欧元，他会被解雇并移交给警方。 最初，Gustaw 的账户中有 $1$ 欧元。请帮助他在不超过 $105$ 次操作的情况下，找出 $M$ 的确切值，并且不要让他被解雇。

每个测试点包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 1000$）。 对于每个测试用例，在你第一次查询之前没有输入，但可以确定 $M$ 是整数，且 $0 \le M \le 10^{14}$。

对于每个测试用例，当你确定 $M$ 的确切值时，输出一行，格式为 "! $M$"。之后你的程序应继续处理下一个测试用例，或在最后一个测试用例后终止。 交互说明 当你想进行一次操作时，输出一行，格式为 "? $X$"，表示你尝试转移 $X$ 欧元（$1 \le X \le 10^{14}$）。作为回应，你会读到一行，可能为以下值之一： - "Lucky!"，如果 $X \le M$。你的余额增加 $X$。 - "Fraudster!"，如果 $X > M$。你的余额减少 $X$。 - "Fired!"，如果 $X > M$，但你无法支付 $X$ 欧元的罚款。在这种情况下，你的程序必须立即终止。如果你超过了查询次数限制，也会收到该响应。 每个测试用例最多可以进行 $105$ 次此类查询。 每次输出查询后，不要忘记输出换行并刷新输出。否则，你会收到 Idleness limit exceeded 的错误。可以使用以下方法刷新输出： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请参考相关文档。 Hack 说明 要制作 hack，请准备如下格式的输入。 第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。 每个测试用例用一行描述，包含一个整数 $M$（$0 \le M \le 10^{14}$）。

在示例中，$M = 5$，因此当 $X = 6$ 时操作被检测到。此时，Gustaw 的余额为 $16$ 欧元，所以他只需支付罚款。 由 ChatGPT 4.1 翻译