题目描述

题目译自 PA 2016 Runda 3 Ciepło-zimno

小 Krotka 和她的哥哥 Entek 是某个 $d$ 维世界的快乐居民。今天，他们决定玩捉迷藏游戏——首先由 Entek 来寻找。由于在高维世界中寻找并不容易，为了简化游戏，他们决定通过对讲机沟通。此外，他们都携带了 GPS 接收器。

Krotka 藏在超立方体森林的某个格点（即所有坐标均为整数的点），并且在游戏结束前不会移动。森林正如其名，是一个边长为 $r$ 的超立方体——包含所有坐标在 $[0, r]$ 范围内的点。Entek 在寻找妹妹时，会在森林中移动，偶尔通过 GPS 向她报告自己的位置。我们假设 Entek 在报告位置时总是位于一个格点。

在 Entek 报告自己的位置后，他会收到 Krotka 的回复「热」或「冷」——Krotka 会告诉他是否比上次联系时更靠近她的位置。

对于 $d$ 维点 $p, x, y$，Krotka 认为点 $x$ 比点 $y$ 更靠近点 $p$，当且仅当：

$$\max_{i=1,2,\ldots,d} |x_{i} - p_{i}| < \max_{i=1,2,\ldots,d} |y_{i} - p_{i}|. $$

Entek 的对讲机电池容量有限，最多允许他进行 $k$ 次通话。请帮助他在失去与妹妹联系之前找到她。

交互方式

Krotka 藏在 $d$ 维空间中一个所有坐标均为整数且在 $[0, r]$ 范围内的点。在游戏期间，Krotka 会如实回答，并且不会移动。

你的程序应使用提供的模拟 Krotka 回复的库文件。在 C 或 C++ 编写的解决方案中，需在程序中加入：

#include "cielib.h"

对于 Java 解决方案，库文件将自动包含，无需在源文件中添加额外代码。

与库文件的通信通过以下函数进行：

• int podajD() - 返回 Krotka 和 Entek 所在世界的维度，即上文提到的 $d$。
• int podajK() - 返回可以调用 czyCieplo 的次数，即上文提到的 $k$。
• int podajR() - 返回超立方体森林的边长，即上文提到的 $r$。
• int czyCieplo(int pozycja[]) - pozycja 必须是一个包含 $d$ 个元素的整数数组，元素值在 $[0, r]$ 范围内，表示 Entek 的当前位置。该函数始终返回 $0$ 或 $1$。在程序运行期间，该函数最多可被调用 $k$ 次。首次调用时，函数返回 $0$。在后续调用中，当且仅当 Entek 当前位置比上一次调用时更靠近 Krotka 的位置时，返回 $1$。
• void znalazlem(int pozycja[]) - pozycja 必须是一个包含 $d$ 个元素的整数数组，元素值在 $[0, r]$ 范围内，表示找到的 Krotka 的位置。该函数必须且只能调用一次，调用后程序将结束运行。

在 C 和 C++ 中，这些是全局函数；在 Java 中，这些是 cielib 类的静态方法（例如：cielib.podajD()）。

你的程序不得打开任何文件，也不得使用标准输入和输出。解决方案将与库文件一起编译，命令如下：

• C：gcc -std=c11 -static -O2 -s cielib.c cie.c -lm
• C++：g++ -std=c++11 -static -O2 -s cielib.c cie.cpp -lm
• Java：

javac cie.java
jar cf cie.jar *.class

在「文件」中，你可以找到示例库文件和错误的解决方案，展示其使用方式。为使上述编译命令有效，库文件应位于当前目录中。

评分规则

如果你的程序在最多 $k$ 次调用 czyCieplo 函数后，以正确的 Krotka 位置调用 znalazlem 函数，则该测试获得分数。如果程序错误使用库文件（调用函数时参数不符合「交互方式」中的要求，或使用标准输入或输出），则该测试获得 $0$ 分。

样例

函数调用	返回值
podajD()	$2$
podajK()	$200$
podajR()	$2$
czyCieplo({0, 0})	$0$
czyCieplo({1, 1})	$1$
czyCieplo({2, 2})	$1$
znalazlem({2, 2})	程序成功结束。

数据范围与提示

对于所有输入数据，满足 $2 \leq r \leq 10^{9}$，$1 \leq d \leq 500$，$k \geq 100d$。