AdditionalFile5769.zip

#5769. 「CEOI2026」寻宝

标签: 交互 | 时间限制: 8000 ms | 内存限制: 256 MiB |

题目描述

题目译自 CEOI 2026 Day1 T3「Treasure Hunt」

你正在拿着一面神奇的指南针，在一个巨大的 $N \times N$ 网格格子上寻找失落已久的宝藏。网格中共有 $K \leq 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$

在上例中：

1. 首先调用 NextHunt(N, K) 开启一次寻宝，得到 $N = 4, K = 1$。
2. 查询格子 $(2, 0)$，指南针指示向右和向下移动都可以到达最近的宝藏，返回值加和为 DIR_DOWN + DIR_RIGHT $= 8 + 1 = 9$。
3. 查询格子 $(3, 1)$，指南针指示向下移动，返回 DIR_DOWN $= 8$。
4. 查询格子 $(3, 2)$，指南针指示该格子本身即包含宝藏，返回 TREASURE $= 0$。
5. 再次调用 NextHunt(N, K)，返回 $N = -1, K = -1$，表示没有更多寻宝任务，程序随后正常结束。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10^6$
• $1 \leq K \leq 3$
• 在程序的单次运行中，最多包含 $100000$ 次寻宝任务。
• 在单次寻宝任务中，你最多可以进行 $1000$ 次查询。
• 评测系统是非适应性（non-adaptive）的。

一个子任务可能包含多个测试用例（即程序的多次运行），而每个测试用例又可能包含多次寻宝任务。出于评分目的，给定子任务中的所有寻宝任务都会被集中统一评估，无论它们最初是如何划分到各个测试用例中的。对于第 $i$ 次寻宝任务，记网格大小为 $N_i \times N_i$，宝藏数量为 $K_i$，你的程序做出的查询次数为 $Q_i$，你的程序找到的宝藏数量为 $F_i$。再记该子任务的总分值为 $S$。则你的程序在该子任务中获得的分数为：

• 若你的程序总是找齐了所有宝藏（即对于所有 $i$ 均有 $F_i = K_i$），则得分取决于 $t_i = \frac{Q_i}{\lceil \log_2 N_i \rceil}$：

$$\frac{S}{2} + \frac{S}{2} \cdot \min_i f(t_i) \text{ 分，其中 } f(t_i) = \begin{cases} 1, & t_i \leq 11 \\ 1 - (t_i - 11) / 9, & 11 \leq t_i \leq 20 \\ 0, & t_i \geq 20 \end{cases}$$

• 若你的程序未能总是找齐所有宝藏（即存在某个 $i$ 使得 $F_i < K_i$），则获得：

$$\frac{S}{2} \cdot \min_i \frac{F_i}{K_i} \text{ 分。}$$

换句话说，找齐所有宝藏可以获得一半的分数，而以尽可能少的查询次数找到它们可以获得另一半的分数。若要获得满分，你的解法应当在最多 $11 \lceil \log_2 N_i \rceil$ 次查询内找到所有宝藏。在 $11 \lceil \log_2 N_i \rceil$ 到 $20 \lceil \log_2 N_i \rceil$ 次查询之间，得分将线性递减；若你的解法使用了超过 $20 \lceil \log_2 N_i \rceil$ 次查询，则只能获得找齐所有宝藏的前一半分数。（符号 $\lceil \cdot \rceil$ 表示对 $\log_2 N_i$ 的值向上取整到最接近的整数。）

若上述公式计算出的子任务得分不是整数，则会四舍五入到最接近的整数。

若你的程序发生运行错误（RTE）或未能遵守上述使用交互库的协议，则整个子任务将获得 $0$ 分。因此，若要通过寻找一部分宝藏来获取部分分，你的程序需要通过调用 NextHunt 来优雅地结束搜索。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$10$	$K = 1$
$2$	$30$	$K = 2$
$3$	$60$	$K = 3$