← 返回题目列表

Codeforces · 1470/C

C. 奇怪的洗牌

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

这是一个交互问题。

$$$n$$$ 围成一圈的人正在尝试洗牌。玩家的编号从 $$$1$$$ 到 $$$n$$$,因此玩家 $$$i$$$ 和 $$$i+1$$$ 是邻居(以及玩家 $$$1$$$ 和 $$$n$$$)。他们每个人都有恰好 $$$k$$$ 牌,其中 $$$k$$$ 是偶数。玩家 $$$i$$$ 的左邻居是玩家 $$$i - 1$$$,右邻居是玩家 $$$i + 1$$$(玩家 $$$1$$$ 和 $$$n$$$ 除外,他们是各自的邻居)。

每回合都会发生以下情况:如果玩家有 $$$x$$$ 卡,他们会将 $$$\lfloor x / 2 \rfloor$$$ 给左边的邻居,将 $$$\lceil x / 2 \rceil$$$ 卡给右边的邻居。所有玩家都会同时发生这种情况。

然而,一名玩家 $$$p$$$ 是冒名顶替者,他们只是将所有牌交给右边的邻居。您知道玩家数量 $$$n$$$ 以及每个玩家最初拥有的牌数 $$$k$$$,但您不知道 $$$p$$$。您的任务是通过提出诸如“玩家 $$$q$$$ 有多少张牌?”之类的问题来确定 $$$p$$$ 的价值。对于您选择的索引 $$$q$$$。每问完一个问题后,所有玩家都将精确地执行一步,并将他们的牌交给他们的邻居。您需要通过提出不超过 $$$1000$$$ 的问题来找到冒名顶替者。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$4 \le n \le 10^5$$$, $$$2 \le k \le 10^9$$$, $$$k$$$ 是偶数) — 玩家数量和牌数。

互动

您可以通过打印“? $$$q$$$”来提问。这个问题的答案是玩家 $$$q$$$ 现在拥有的牌数 ($$$1 \le q \le n$$$)。洗牌过程在您的第一个问题之后立即开始,因此第一个问题的答案始终等于 $$$k$$$。

一旦你识别出冒名顶替者,你可以通过打印“!$$$p$$$”来输出答案,其中$$$p$$$是冒充者的玩家($$$1 \le p \le n$$$)。然后你必须终止你的程序。

您必须通过提出不超过 $$$1000$$$ 的问题来找到冒名顶替者。

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

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

黑客

要进行破解,请使用以下测试格式。

输入的唯一行应包含三个整数 $$$n$$$、$$$k$$$ 和 $$$p$$$ ($$$4 \le n \le 10^5$$$, $$$2 \le k \le 10^9$$$, $$$k$$$ 为偶数,$$$1 \le p \le n$$$) — 人数,每人卡片数量人最初有,冒名顶替者的位置。

示例

输入 #1

4 2

2

1

2

3

2

输出 #1

? 1

? 1

? 2

? 3

? 4

! 2

注意

在示例中,卡按以下方式传输:

- $$$2$$$ $$$2$$$ $$$2$$$ $$$2$$$ — 玩家 $$$1$$$ 有 $$$2$$$ 卡。
- $$$1$$$ $$$2$$$ $$$3$$$ $$$2$$$ — 玩家 $$$1$$$ 有 $$$1$$$ 卡。

本回合后,每位玩家的卡牌数量保持不变。