本题要在一张非常大的网格上寻找 $k\le 3$ 个宝藏。一次询问 $(x,y)$ 会返回若干个方向；从 $(x,y)$ 沿其中某个方向出发，可以沿一条最短路到达某个最近的宝藏。主要困难在于：寻找一个宝藏时，其他宝藏可能给出误导性的方向。

子任务 1

只有一个宝藏时很简单。分别进行一次二分搜索，确定宝藏所在的列与行；事实上，这两个搜索甚至可以同时完成。

子任务 2

现在要在另一个宝藏的干扰下找出第一个宝藏 $T$。同时搜索它的行和列可能被带偏，因此先确定列，再确定行。

可以从任意位置开始，根据第一次询问返回的方向水平移动。不妨假设方向为向右。通过二分搜索找到某个含有宝藏的列：搜索一对相邻格子的分界，左边的格子含有向右的指示，而其右侧相邻格子不含该指示；后一格所在的列必然包含宝藏。随后，在这一列内用相同方法向上或向下移动。若向上搜索，就寻找这样一对相邻格子的分界：下面的格子含有向上的指示，而上面的相邻格子不含；后者一定是某个宝藏。

找到第一个宝藏 $T$ 后，两条经过 $T$ 的对角线把平面分成右、左、上、下四个区域。我们分别在四个区域内搜索第二个宝藏 $U$。例如，从 $T$ 出发沿同一行向右搜索。起初，一些格子会向左指向第一个宝藏；一旦指示发生变化，就说明已经接近第二个宝藏。可以按递增的二次幂长度进行倍增，确定发生变化的大致位置，再进行一次二分搜索，精确找出某个向上或向下指向第二个宝藏的格子。这样便确定了宝藏所在的列，再在该列内二分搜索其所在的行。

需要特别处理两个宝藏位于同一行，以及两个宝藏恰为某个正方形的一对对角顶点等边界情况。

子任务 3

前面已经说明了如何找到第一个宝藏 $T$；存在三个宝藏时，同样的策略依然适用。

搜索第二个宝藏时，同一区域内可能有多个宝藏，例如它们都位于右侧。此前，我们从 $T$ 沿同一行搜索某个包含第二个宝藏的列；现在则希望更精确地找到最近的那个宝藏。令 $B$ 为 $T$ 右侧最近的、返回方向不只有向左的格子。可以确定，另外两个宝藏之一位于以 $B$ 为中心的菱形边界上。先在 $B$ 右侧的同一行内二分搜索，找到某个包含第二个宝藏的列，再在该列内向上或向下二分搜索。

假设找到了位于点 $C$ 的第二个宝藏，而且 $C$ 如预期那样位于这个菱形上。可以从 $C$ 出发，在上、下、右三个区域内用类似方法搜索第三个宝藏。

否则，我们能够确定第三个点所在的一条线段，但实际却在更远的点 $D$ 找到了某个宝藏。此时可以从 $D$ 沿两个方向进行类似搜索，因为由 $B$ 确定的菱形边，与 $D$ 的区域划分至多相交于两个区域。最后一个宝藏的位置可以由两条线段的交点确定。

还要注意 $T$ 与 $U$ 位于同一条对角线的情况。此时，它们可能彼此都能被对方找到，却始终找不到第三个宝藏。

上述方法至多使用 $17\log n$ 次询问，还可以进一步优化到至多 $11\log n$ 次。例如，结合最先找到的两个宝藏的相对方向，可以减少定位最后一个宝藏所需的二分搜索次数。一种优化方法是考虑第二个宝藏在网格四条边界上的投影。询问这些投影点后，可以迅速判断第三个宝藏位于哪个区域，或判断它是否与 $U$ 位于同一行或同一列。

生成式人工智能辅助说明

本文由 OpenAI Codex 根据用户提供的 CEOI 2026 第一日官方英文题解翻译、排版并统一数学公式格式；算法思路、论证与复杂度均来自原文，未另行生成新的解法。