CEOI 2026 Day 1

时间限制：8 秒
内存限制：256 MiB
题目类型：交互式 / 函数调用式，带查询次数评分

题目描述

你正在一个 $N\times N$ 的网格中寻找失落已久的宝藏。网格中藏有 $K$ 个宝箱，其中

$$K\le 3,$$

并且所有宝箱位于互不相同的格子中。

你拥有一个魔法指南针。把指南针放在格子 $(x,y)$ 后，它会寻找曼哈顿距离最近的宝箱，并指出某条最短路径的第一步方向。允许的移动方向为左、上、右、下。

若存在多个同样近的宝箱，或者前往最近宝箱存在多种合法的第一步，指南针会返回所有可能方向。若当前格子本身放有宝箱，指南针会直接指出这里有宝箱。

每当你找到一个宝箱时，你会取走其中的宝物，但不会移走宝箱本身。指南针无法区分宝箱是否已被取空，因此之后仍可能继续指向已经找到的宝箱。

你的目标是找到所有宝箱，并尽可能减少指南针查询次数。

交互接口

本题通过组织者提供的库进行交互。程序必须包含：

#include "treasurehuntlib.h"

库中提供以下接口和常量。

NextHunt

void NextHunt(int &N, int &K);

调用该函数开始下一次独立的寻宝：

• 函数会把网格大小写入 $N$，把宝箱数量写入 $K$；
• 若本次程序运行中已经没有更多寻宝任务，则会令 $N=K=-1$；
• 此时程序必须以退出码 $0$ 正常结束。

即使尚未找到当前任务中的全部宝箱，也允许提前调用 NextHunt 进入下一次任务，但会损失得分。

方向常量

enum {
    TREASURE = 0,
    DIR_RIGHT = 1,
    DIR_UP = 2,
    DIR_LEFT = 4,
    DIR_DOWN = 8
};

Query

int Query(int x, int y);

其中 $0\le x,y<N$。

• 若格子 $(x,y)$ 中有宝箱，返回 TREASURE；
• 否则，返回一个或多个方向常量之和，表示从该格子出发，哪些方向可以作为通向某个最近宝箱的最短路径的第一步。

本题坐标系中，$y$ 坐标从上向下增大。

例如，返回值

DIR_DOWN + DIR_RIGHT = 9

表示向下和向右都可能是合法的第一步。

交互规则

• 第一次调用必须是 NextHunt，在此之前不得调用 Query；
• 当 NextHunt 返回 $N=K=-1$ 后，不得再调用任何接口；
• 每次寻宝中最多调用 Query 1000 次；
• 查询坐标必须满足 $0\le x,y<N$；
• 若违反协议，评测库会终止程序，对应测试得到运行时错误；
• 程序不得从标准输入读取，也不得向标准输出写入；标准输入输出由评测库内部使用；
• 评测系统是非自适应的，即宝箱位置不会根据你的查询动态改变。

一个宝箱被视为“找到”，当且仅当程序至少查询过一次该宝箱所在的格子。

原题同时提供公开版本的库实现 treasurehuntlib-public.cpp，可使用类似命令在本地编译：

g++ foo.cpp treasurehuntlib-public.cpp

正式评测使用的库实现与公开版本不同，不应依赖公开实现的内部细节。

数据范围

• $1\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=\left\lceil\frac{Q_i}{\lceil\log_2 N_i\rceil}\right\rceil.$$

该子任务得分为

$$\frac S2+\frac S2\cdot\min_i f(t_i),$$

其中

$$f(t)= \begin{cases} 1, & t\le 11,\\ 1-\dfrac{t-11}{9}, & 11\le t\le 20,\\ 0, & t\ge 20. \end{cases}$$

也就是说：

• 若每次寻宝都使用不超过 $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$ 次时，只能获得“找全宝箱”对应的一半分数。

未能始终找全宝箱

若存在某次寻宝满足 $F_i<K_i$，该子任务得分为

$$\frac S2\cdot\min_i\frac{F_i}{K_i}.$$

若计算结果不是整数，四舍五入到最接近的整数。

若程序发生运行时错误或违反交互协议，则整个子任务得 $0$ 分。即使只争取找到部分宝箱，也必须通过调用 NextHunt 正确结束当前任务并继续处理后续任务。

交互示例

程序调用	库返回值或写入值
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

交互2