背景

题目附件来自 QOJ。

题目描述

你正在一片巨大的 $N\times N$ 方格区域中，借助一个魔法罗盘寻找失落已久的宝藏。场地中共有 $K\le 3$ 个宝箱，分别藏在互不相同的格子里。你的目标很简单：找到所有宝箱！

当你把罗盘放在某个格子上时，它会寻找仅通过向左、向上、向右、向下移动而到达某个宝箱的最短路径，也就是寻找曼哈顿距离最近的宝箱。随后，罗盘会显示最短路径第一步的方向。如果有多个合法的第一步可以通向某个最近的宝箱（也可能通向多个最近的宝箱），罗盘会返回所有这些方向。如果当前格子中有宝箱，罗盘则会指出这一点。

每当你找到一个宝箱时，你会取出其中的宝物，但无法移走宝箱，因为它太重了。罗盘不知道某个宝箱是满的还是空的，它总会指向距离最近的宝箱，无论该宝箱为空还是装有宝物。

请尝试用尽可能少的罗盘询问找到所有宝箱的位置。

任务

这是一道交互题。在每个测试用例（即程序的每次运行）中，你的程序都需要完成若干次寻宝。你应当使用主办方提供的库与评测程序交互。该库包含以下声明：

• void NextHunt(int &N, int &K)——调用此函数以开始下一次寻宝。该函数会将网格大小写入变量 $N$，并将宝箱数量写入 $K$。如果本次程序运行中已经没有需要完成的寻宝，该函数会将 $N$ 和 $K$ 都设为 $-1$；此时，你应当立即以退出码 $0$ 终止程序。请注意，你可以在尚未找到当前寻宝中的全部宝箱时调用此函数，例如，你只打算争取部分分数时可以这样做。

• enum { TREASURE = 0, DIR_RIGHT = 1, DIR_UP = 2, DIR_LEFT = 4, DIR_DOWN = 8 };——这些常量用于 Query 函数的返回值，详见下文。

• int Query(int x, int y)——如果坐标为 $(x,y)$ 的格子中有宝箱，此函数返回 TREASURE；否则，它会返回 DIR_RIGHT、DIR_UP、DIR_LEFT 和 DIR_DOWN 中一个或多个常量之和，以表示将罗盘放在格子 $(x,y)$ 上时返回的移动方向。坐标 $x$ 和 $y$ 必须是 $0$ 到 $N-1$ 之间的整数。（注意：在本题中，$y$ 坐标从上向下递增。）

当 NextHunt 将 $N=K=-1$ 后，程序不得再次调用 NextHunt 或 Query；在第一次调用 NextHunt 之前，程序也不得调用 Query。如果程序违反这些限制，单次寻宝中发起超过 $1000$ 次询问，或者调用 Query 时传入了越界的 $x$ 和/或 $y$，该库将终止程序，并使当前测试用例得到运行时错误（RTE）的评测结果。

如果你曾至少一次询问到某个宝箱所在的格子，就认为该宝箱已被找到。如果程序在找到当前寻宝的所有宝箱之前调用 NextHunt，这不会被视为错误，但会影响程序得分，详见下文的计分方式。

要使用该库，程序应包含头文件 treasurehuntlib.h：

    #include "treasurehuntlib.h"

你可以在此处下载该头文件：treasurehuntlib.h。

为了帮助你开发解决方案，此处还提供了该库的一个简单实现：treasurehuntlib-public.cpp。要将它与程序一起编译，只需把它的文件名作为参数传给编译器。例如：

    g++ foo.cpp treasurehuntlib-public.cpp

这里，foo.cpp 是包含你的解决方案的文件名。

除上述声明外，treasurehuntlib-public.cpp 中的实现还支持一个名为 void InitFromFile(const char *fileName) 的函数。该函数会从文件中读取一系列寻宝数据，使你可以在这些数据上进行游戏，而不是由该实现自行随机生成寻宝数据。你可以在 treasurehuntlib-public.cpp 文件中找到更多细节。

评测服务器会使用该库的另一种实现，因此你不应对其具体工作方式作出任何假设。不过，你可以假定，除上文列出的 NextHunt、Query 和五个常量外，该实现不会向全局命名空间中引入任何其他声明。

你的代码不得从标准输入读取，也不得向标准输出写入，因为评测服务器上的库实现会使用它们与评测环境的其他部分通信。

提示

样例

调用	返回值
NextHunt($N$, $K$)	$N=4$，$K=1$
Query($2$, $0$)	DIR_DOWN $+$ DIR_RIGHT $=9$
Query($3$, $1$)	DIR_DOWN
Query($3$, $2$)	TREASURE
NextHunt($N$, $K$)	$N=-1$，$K=-1$

限制条件

• $2\le N\le 10^6$
• $1\le K\le 3$
• 在程序的单次运行中，寻宝次数至多为 $100\,000$。
• 在单次寻宝中，最多可以发起 $1000$ 次询问。
• 评测系统不具有自适应性。

子任务

• 子任务 $1$（$10$ 分）：$K=1$
• 子任务 $2$（$30$ 分）：$K=2$
• 子任务 $3$（$60$ 分）：$K=3$。

计分方式

一个子任务可能包含多个测试用例（即程序运行多次），而每个测试用例又可能包含多次寻宝。计分时，同一子任务中的所有寻宝会合并评估，而不考虑它们原本如何分布在不同测试用例中。对于第 $i$ 次寻宝，记网格大小为 $N_i\times N_i$，宝箱数量为 $K_i$，程序发起的询问次数为 $Q_i$，程序找到的宝箱数量为 $F_i$。再以 $S$ 表示该子任务的总分。程序在该子任务中获得的分数如下：

• 如果程序每次都找到了所有宝箱，即对所有 $i$ 均有 $F_i=K_i$，则得分取决于 $t_i=\dfrac{Q_i}{\lceil\log_2N_i\rceil}$：

$$\begin{aligned} \frac{S}{2}+\frac{S}{2}\cdot\min_i f(t_i),\qquad f(t_i)&= \begin{cases} 1, & t_i\le 11,\\ 1-(t_i-11)/9, & 11\le t_i\le 20,\\ 0, & t_i\ge 20. \end{cases} \end{aligned}$$

• 如果程序并非每次都找到了所有宝箱，即存在某个 $i$ 满足 $F_i<K_i$，则程序获得 $\dfrac{S}{2}\cdot\min_i\dfrac{F_i}{K_i}$ 分。

换言之，找到全部宝箱可以获得一半分数，使用尽可能少的询问找到它们则决定另一半分数。要获得满分，解决方案应在至多 $11\lceil\log_2N_i\rceil$ 次询问内找到所有宝箱。当询问次数介于 $11\lceil\log_2N_i\rceil$ 与 $20\lceil\log_2N_i\rceil$ 之间时，得分线性下降；如果解决方案使用了超过 $20\lceil\log_2N_i\rceil$ 次询问，则只能获得因找到全部宝箱而给出的前一半分数。（符号 $\lceil\cdot\rceil$ 表示将 $\log_2N_i$ 的值向上取整为最接近的整数。）

如果以上公式算出的子任务分数不是整数，则会四舍五入到最接近的整数。

如果程序发生运行时错误，或没有遵守上文规定的库调用协议，则整个子任务得 $0$ 分。因此，若要因找到部分宝箱而获得部分分数，程序必须调用 NextHunt，从而正常结束本次搜索。

翻译由 ChatGPT-5.6 完成