P12099 [NERC2024] Hunting Hoglins in Hogwarts

这是一道交互题。 Harry 和 Hermione 正在猎捕潜伏在霍格沃茨的 **霍格林**。霍格沃茨有一条长长的走廊，由 $n$ 个独立的**单元格**组成，从左到右编号为 $1$ 到 $n$。 Hermione 可以施展咒语**封锁**她选择的任意一个单元格。一旦施法，该单元格将持续处于封锁状态，直到该轮结束，即使她随后继续施展其他咒语。 霍格林是一种很简单的生物，它们只会随机移动并撞上障碍。更准确地说，每只霍格林都有一个它认为可以活动的**可达范围**。最初，当霍格林出现时，它的可达范围是整个走廊，即第 $1$ 到第 $n$ 个单元格。 每一只霍格林初始随机地出现在走廊中的某个单元格内。之后，在猎捕过程中，每一轮按照如下流程进行： - Hermione 可以选择一个单元格进行封锁，或者什么都不做； - 如果她试图封锁的单元格正好是霍格林所在的位置，那么霍格林就被捕获。随后所有被封锁的单元格被解除封锁，如果还有霍格林待抓捕，则一只新的霍格林立即随机出现，猎捕继续进行； - 否则，霍格林会从它的当前**可达范围**中随机选择一个单元格，试图向该单元格移动，该移动将在同一轮内完成，无论其距离多远，具体过程如下： - 如果目标单元格在当前霍格林位置的右侧，则霍格林向右移动；如果在左侧，则向左移动；若目标与当前位置相同，则不移动； - 在向目标移动的过程中，若霍格林从某个未封锁的位置 $i$ 试图前往其相邻的封锁位置 $i \pm 1$，则霍格林将更新其可达范围的右边界或左边界为 $i$； - 如果霍格林在前往目标单元格的路途中**撞上**了封锁单元格，则 Harry 和 Hermione 会听到一声巨响，此时霍格林会回到本轮开始时的初始位置； - 否则，如果途中没有撞到封锁单元格，则霍格林成功移动至目标位置，并保留原有的可达范围。Harry 和 Hermione 什么也不会听到。 为了彻底清除霍格沃茨中的霍格林，Harry 和 Hermione 需要抓到 $k$ 只霍格林，但时间有限。他们最多只能进行 $200\,000$ 轮操作。请帮助他们设计高效的策略。 ### 交互协议说明 首先，评测器会输出两个整数 $n$ 和 $k$（$1 \le n \le 10^{18}$，$1 \le k \le 800$），分别表示走廊的长度和需要抓捕的霍格林数量。接下来开始进行猎捕。 之后交互按轮进行，每轮遵循题目描述的流程： - 你的程序需输出一个整数 $p$（$0 \le p \le n$），表示 Hermione 本轮选择封锁的位置。如果 $p=0$ 或 $p$ 所在单元格已被封锁，则 Hermione 本轮不进行操作。 - 若当前霍格林正好位于被封锁的位置 $p$，则该霍格林被捕获，评测器输出 $\texttt{2}$，所有封锁单元格解除，并立即生成新的霍格林，猎捕继续进行； - 若这是第 $k$ 个被捕获的霍格林，评测器输出 $\texttt{3}$，你的程序应立即退出。 - 若未抓到霍格林，评测器将模拟霍格林的移动并输出如下之一： - $\texttt{0}$：霍格林成功移动到目标位置，途中没有撞击； - $\texttt{1}$：霍格林在移动途中撞到了封锁单元格，发出声响并返回原位。 - 若你的程序在第 $200\,000$ 轮仍未成功抓到第 $k$ 个霍格林，评测器将输出 $\texttt{-1}$，你的程序应立即退出，否则将判定为 `Wrong Answer`。

详见 **交互协议说明**。

详见 **交互协议说明**。

下图展示了从霍格林的视角观察的一个示例状态： - 黑点表示当前霍格林的位置； - 十字表示被封锁的单元格； - 白色区域表示霍格林认为的可达范围； - 灰色区域为其不可达区域； - 图右侧注释了 Hermione 或霍格林执行的操作，导致状态变化。