P13123 [GCJ 2019 Finals] Board Meeting [Can't Judge yet]
题目描述
注意，解决本题并不需要了解国际象棋的规则。
在一个无限大的国际象棋棋盘（二维网格）上，有 $N$ 个国王，分别位于坐标 $(X_{1}, Y_{1})$，$(X_{2}, Y_{2})$，...，$(X_{N}, Y_{N})$。你并不知道 $N$ 以及这些国王的具体坐标，但你知道以下信息：
- $N$ 至少为 $1$，至多为 $N_{\text{max}}$。
- 没有任何一个国王的坐标（$X$ 或 $Y$）的绝对值超过 $M$。
- $N$ 个国王分别位于 $N$ 个不同的格子中。
这些国王想要在棋盘上的某一个格子会合。如果选择某个格子 $(X, Y)$ 作为会合点，则第 $i$ 个国王到达该点所需的步数为其当前位置与会合点坐标差的绝对值的最大值：$\max(|X-X_{i}|, |Y-Y_{i}|)$。所有国王到达会合点所需的总步数就是对所有 $i$ 的上述最大值之和。注意，本题并不关心国王具体如何移动——只关心起点和终点，以及步数的计算方式。
本题分为两个阶段。在第一阶段，你可以多次进行如下操作：提出一个会合点 $(A, B)$（其中 $A$ 和 $B$ 均在 $-10 \times M$ 到 $10 \times M$ 之间，包括端点），裁判会告诉你所有国王到达该点所需的总步数——即对所有 $i$ 计算 $\max(|X_{i}-A|, |Y_{i}-B|)$ 的和。你最多可以进行 $R$ 次这样的交互，每次可以自由选择 $A$ 和 $B$ 的值。注意，国王并不会真的移动，所以在同一测试用例的所有请求中，国王的位置 $(X_{i}, Y_{i})$ 都保持不变。
在第二阶段，角色互换：裁判会给你一个会合点 $(C, D)$（其中 $C$ 和 $D$ 均在 $-10 \times M$ 到 $10 \times M$ 之间，包括端点），你需要回答所有国王到达该点所需的总步数，假设国王们的位置与第一阶段相同。裁判最多会发出 $R$ 个这样的请求，你需要全部正确回答。
### 交互协议
这是一个交互题。
程序开始时，你需要读取一行，包含四个整数 $T$、$N_{\text{max}}$、$M$ 和 $R$，分别表示测试用例数、国王数量的最大值、任意国王坐标的最大绝对值、每个阶段最多请求次数。（注意 $M$ 和 $R$ 的值是固定的，仅为方便输入，具体见限制部分。）然后，你需要依次处理 $T$ 个测试用例。
每个测试用例包含两个阶段。在第一阶段，第 $i$ 次交互如下：
- 你的程序输出一行，包含两个整数 $A_{i}$ 和 $B_{i}$，表示一个格子的 $x$ 和 $y$ 坐标。
- $A_{i}$ 和 $B_{i}$ 必须都在 $-10 \times M$ 到 $10 \times M$ 之间，包括端点。
- 裁判回复一行，包含一个整数：所有国王从未知位置到你指定的格子所需的总步数。
你在本阶段最多可以进行 $R$ 次这样的交互。如果你超过 $R$ 次，或者请求格式错误或越界，裁判会回复一行字符串 $\text{ERROR}$。
当你想结束第一阶段并进入第二阶段时，输出一行字符串 $\text{READY}$（大小写不敏感），裁判会回复第二阶段的第一个请求。
在第二阶段，第 $i$ 次交互如下：
- 裁判输出一行，包含两个整数 $C_{i}$ 和 $D_{i}$，表示一个格子的 $x$ 和 $y$ 坐标。
- $C_{i}$ 和 $D_{i}$ 都在 $-10 \times M$ 到 $10 \times M$ 之间，包括端点。
- 你的程序需要输出一行，包含一个整数：所有国王到达该点所需的总步数。
裁判保证会发出至少 $1$ 次、至多 $R$ 次这样的请求。如果你的回答错误或格式不正确，裁判会回复 $\text{ERROR}$。如果你全部回答正确，裁判会回复一行字符串 $\text{DONE}$，此时你应开始下一个测试用例，或在所有 $T$ 个测试用例处理完毕后正常结束程序。
如果裁判回复 $\text{ERROR}$，则不会再有其他输出。如果你的程序在收到 $\text{ERROR}$ 后继续等待裁判输出，将会超时（Time Limit Exceeded）。请确保你的程序在收到 $\text{ERROR}$ 后及时退出，以便获得 Wrong Answer 而不是 TLE。如果超出内存限制或运行时错误，将会收到相应的判定。
国王的数量和位置，以及第二阶段裁判发出的请求数量和位置，在所有交互开始前就已确定。
输入格式
见交互协议。
输出格式
见交互协议。
说明/提示
**交互样例**
注意，以下交互样例对应于测试集 1，其中总是只有一个国王。
```
// 假设裁判决定第一个测试用例中，国王在坐标 (1, -2)，请求为 (5, -1) 和 (7, 7)。
t, nmax, m, r = readline_int_list() // 读取 10 1 1000000 1000
// 我们的解法（无论出于什么原因）首先查询 (3, 3)。
printline 3 3 to stdout
flush stdout
result = readline_int() // 读取 5
// 现在查询 (2, 0)。
printline 2 0 to stdout
flush stdout
result = readline_int() // 读取 2
// 我们推断国王在 (3, -2)，这与已知信息一致，但实际上不正确。
// 进入请求阶段。
printline READY to stdout
request_line = readline() // 读取 5 -1
printline 2 to stdout // 错误答案！
request_line = readline() // 读取 ERROR
exit // 退出，避免 TLE
```
你可以使用本地或平台提供的测试工具进行测试。若要在本地测试，需要让测试工具与你的代码并行运行；你可以使用我们的 [interactive runner](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)。更多信息请阅读该文件中的注释。
测试工具的使用说明见工具内注释。建议你自行添加测试用例。请注意，测试工具仅用于模拟评测系统，**并非**真实评测系统，可能存在差异。
**限制条件**
~~仅进行合法交互的程序，在我们的环境下运行时间约为：C++ 13 秒，Java 24 秒，Python 和 Go 19 秒。~~
- $1 \leq T \leq 15$。
- $M = 10^{6}$。
- $-\mathbf{M} \leq X_{i} \leq \mathbf{M}$，对所有 $i$。
- $-\mathbf{M} \leq Y_{i} \leq \mathbf{M}$，对所有 $i$。
- 所有 $(X_{i}, Y_{i})$ 均互不相同。
- $-10 \times M \leq C_{i} \leq 10 \times M$，对所有 $i$。
- $-10 \times M \leq D_{i} \leq 10 \times M$，对所有 $i$。
- $R = 1000$。
**测试集 1（5 分，可见）**
- $N_{\text{max}} = 1$。
**测试集 2（22 分，隐藏）**
- $N_{\text{max}} = 10$。
由 ChatGPT 4.1 翻译