← 返回题目列表

Codeforces · 2174/E2

E2. 科学家的游戏(版本 2)

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

这两个版本对$$$k$$$、$$$c$$$有不同的约束。解决两个版本之一不一定能解决另一个版本。您可能想阅读这两个版本。两个版本都禁用了黑客攻击。

这是一个交互问题。

在奥斯曼帝国时期,许多科学家都在工作。你决定研究他们的日常生活,并偶然发现了当时流行的一个有趣的游戏。一位科学家会想到一个整数 $$$x$$$,例如 $$$1 \leq x \leq c$$$。另一位科学家会尝试猜测它。他可以指定数字系统的基数 $$$2 \leq b \leq c$$$,并且如果 $$$x \geq b$$$,则接收 $$$x$$$ 在基数 $$$b$$$ 中的数字总和作为响应,如果 $$$x \lt b$$$,则接收 $$$-1$$$。

您编写了一个程序,可以想到数字 $$$x$$$ 并回答问题。现在您想使用它并学习使用 $$$\leq k$$$ 查询进行猜测。

输入

第一行包含三个整数 $$$t$$$、$$$k$$$、$$$c$$$ ($$$1 \leq t \leq 10^4$$$、$$$\mathbf{k=3}$$$、$$$\mathbf{c=2\cdot10^9}$$$)。您必须使用 $$$\leq k$$$ 查询猜测从 $$$1$$$ 到 $$$c$$$ $$$t$$$ 次的数字。所有 $$$t$$$ 游戏将连续进行并且是独立的。

互动

要进行查询,必须输出 ? $$$b$$$ 对于一些 $$$2 \leq b \leq c$$$。然后,您必须读取响应 - 一个整数 $$$a$$$ ($$$-1 \leq a \lt c$$$) - 对查询的响应。

要提供猜测的数字,您必须输出 ! $$$x$$$,其中 $$$1 \leq x \leq c$$$ — 你的答案。然后你必须读取结果 $$$r$$$ ($$$0 \leq r \leq 1$$$)。如果 $$$r = 0$$$ — 您的答案不正确,在这种情况下您必须立即终止程序。否则,如果 $$$r = 1$$$ — 您的答案是正确的,您可以继续下一个游戏,或者如果已经玩过 $$$t$$$ 游戏,则终止程序。

保证交互器不具有自适应性。也就是说,所有选择的号码都是预先固定的,并且在比赛期间不会改变。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取到 -2 而不是有效数据,则您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

3 3 2000000000

1

1

7

1

-1

1

-1

6

6

1

输出
复制

? 10

? 1000

? 2

! 1000000

? 2

! 1

? 100

? 10

? 5

! 42

注意

在第一局游戏中,隐藏数字是$$$1000000_{10} = 100_{1000} = 11110100001001000000_2$$$。这些基数中的数字总和为 $$$1$$$、$$$1$$$ 和 $$$7$$$。

在第二局游戏中,隐藏的数字是$$$1$$$。 $$$b = 2$$$ 的查询返回 $$$-1$$$。

在第三局游戏中,隐藏数字是$$$42_{10} = 132_{5}$$$。