CF1470C Strange Shuffle

这是一个交互题。 有 $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$ 号玩家现在有多少张牌？”（$q$ 可自选）来确定 $p$ 的值。每次询问后，所有玩家都会立即进行一次洗牌操作。你需要在不超过 $1000$ 次询问内找出冒名顶替者。

第一行包含两个整数 $n$ 和 $k$（$4 \le n \le 10^5$，$2 \le k \le 10^9$，$k$ 是偶数），表示玩家人数和每人初始手牌数。

你可以通过输出 "? $q$" 来询问第 $q$ 号玩家当前有多少张牌（$1 \le q \le n$）。该询问的答案是第 $q$ 号玩家此时拥有的牌数。洗牌过程会在你第一次询问后立即开始，因此第一次询问的答案总是 $k$。 一旦你确定了冒名顶替者，可以通过输出 "! $p$" 来给出答案，其中 $p$ 是冒名顶替者的编号（$1 \le p \le n$）。然后你的程序必须终止。 你必须在不超过 $1000$ 次询问内找出冒名顶替者。 每次输出询问后不要忘记输出换行并刷新输出缓冲区，否则会收到“Idleness limit exceeded”的判罚。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档 Hack 格式 制作 Hack 时，输入格式如下： 输入仅一行，包含三个整数 $n$、$k$ 和 $p$（$4 \le n \le 10^5$，$2 \le k \le 10^9$，$k$ 是偶数，$1 \le p \le n$），分别表示人数、每人初始手牌数和冒名顶替者的位置。

在样例中，牌的传递方式如下： - $2\ 2\ 2\ 2$ —— 玩家 $1$ 有 $2$ 张牌。 - $1\ 2\ 3\ 2$ —— 玩家 $1$ 有 $1$ 张牌。 此后，每位玩家的牌数都保持不变。 由 ChatGPT 4.1 翻译