IOI 国政府因 IOI 山频发遭难事故,设立了专门的 IOI 山山岳救助队。设立数日后,救助队收到了一起遭难事故的通报。据通报,遭难者目前停留在高度为 $X$ 的位置。
IOI 山由 $R$ 行 $C$ 列的网格表示,每个网格点都有一个确定的高度值。我们将从上往下数第 $r$ 行、从左往右数第 $c$ 列的网格表示为 $(r, c)$。已知山体形状满足以下条件:
- 不存在两个高度相同的不同网格。
- 每个网格的高度均为 $1$ 以上 $1\,000\,000\,000$ 以下的整数。
- 网格 $(R_S, C_S)$ 是山顶。即高度最大的网格为 $(R_S, C_S)$。
- 定义两个网格 $(r_1, c_1)$ 和 $(r_2, c_2)$ 的距离为 $|r_1 - r_2| + |c_1 - c_2|$。对于任意两个相邻的网格,距离山顶越远,高度越低。其中,两个网格相邻是指它们共享一条边。
由于山岳救助队刚成立不久,对 IOI 山的调查尚不充分,包括山顶在内,各网格的高度均未知。可以使用专业的测量仪器查询指定网格的高度,但查询需要一定时间。希望利用该测量仪器确定遭难者所在高度为 $X$ 的网格位置,但测量仪器的使用次数必须控制在 $1\,000$ 次以内。
题目描述
给定表示 IOI 山网格大小的整数 $R, C$,山顶位置 $R_S, C_S$ 以及遭难者所在网格的高度 $X$,请编写一个程序,通过最多使用 $1\,000$ 次测量仪器来确定遭难者所在网格的位置。
实现细节
你必须编写一个实现了测量仪器使用方法的程序。 程序必须实现以下例程:
void Rescue(int R, int C, int RS, int CS, int X)
该例程对于每个测试用例仅被调用一次。参数 $R, C$ 分别为表示山的网格的行数和列数。参数 $R_S, C_S$ 分别为山顶的行号和列号。参数 $X$ 为遭难者所在网格的高度。
此外,程序中可以调用以下例程:
int Measure(int RM, int CM)
该例程在需要使用测量仪器时调用。参数 $R_M, C_M$ 分别为测量仪器要查询高度的网格的行号和列号。满足 $1 \le R_M \le R, 1 \le C_M \le C$。该例程的返回值为网格 $(R_M, C_M)$ 的高度,是一个 $1$ 以上 $1\,000\,000\,000$ 以下的整数。
如果调用该例程时传入的值不满足 $1 \le R_M \le R, 1 \le C_M \le C$,则判定为“不正解 [1]”,程序终止。 此外,如果该例程在被调用 $1\,000$ 次后再次被调用,则判定为“不正解 [2]”,程序终止。
void Pinpoint(int RP, int CP)
该例程在确定了遭难者所在网格后调用一次。参数 $R_P, C_P$ 分别为确定遭难者所在的网格的行号和列号。满足 $1 \le R_P \le R, 1 \le C_P \le C$。该例程没有返回值。
如果调用该例程时传入的值不满足 $1 \le R_P \le R, 1 \le C_P \le C$,则判定为“不正解 [3]”,程序终止。
当程序调用此例程时,如果网格 $(R_P, C_P)$ 的高度等于 $X$,则判定为“正解”,否则判定为“不正解 [4]”,程序终止。
如果 Rescue 例程在未调用此例程的情况下结束,则判定为“不正解 [5]”,程序终止。
编译与运行方法
用于测试所编写程序的评分程序示例包含在可从竞赛网站下载的压缩包中。该压缩包中也包含了必须提交的文件示例。
评分程序示例由一个文件组成。该文件为 grader.c 或 grader.cpp。要测试所编写的程序,请执行以下命令:
- C 语言的情况
gcc -O2 -lm grader.c mountain.c -o grader - C++ 的情况
g++ -O2 grader.cpp mountain.cpp -o grader
如果编译成功,将生成名为 grader 的可执行文件。
请注意,实际的评分程序与评分程序示例不同。该程序从标准输入读取输入,并将结果输出到标准输出。
输入格式
评分程序示例从标准输入读取以下输入:
- 第 1 行包含整数 $R, C, R_S, C_S, X$,以空格分隔,表示山的网格行数为 $R$,列数为 $C$,山顶为 $(R_S, C_S)$,遭难者所在网格高度为 $X$。
- 接下来的 $R$ 行包含山的高度信息。其中第 $i$ 行 ($1 \le i \le R$) 包含 $C$ 个整数,其中第 $j$ 个 ($1 \le j \le C$) 整数表示网格 $(i, j)$ 的高度。
输出格式
如果程序正常结束,评分程序示例将向标准输出输出以下信息(仅一行):
- 如果是正解,输出 "Accepted"。
- 如果是错误,则根据“实现细节”一节中记载的编号输出错误类型,例如 "Wrong Answer[1]"。此外,对于“不正解 [4]”,会输出正确的遭难者位置 $(R_X, C_X)$ 以及调用
Pinpoint例程时参数指定的网格 $(R_P, C_P)$ 信息,格式为 "Wrong Answer[4] : (RX, CX) = (3, 2), (RP, CP) = (4, 1)"。
数据范围
所有输入数据满足以下条件:
- $1 \le R \le 200$
- $1 \le C \le 200$
- $1 \le R_S \le R$
- $1 \le C_S \le C$
- $1 \le X \le 1\,000\,000\,000$
子任务
子任务 1 [20 分]
满足以下条件: $R \le 50$ $C \le 50$
子任务 2 [80 分]
无额外限制。
样例
以下是评分程序示例读取的输入示例,以及对应的例程调用示例。
输入 1
5 5 3 3 76 14 59 84 62 28 15 73 92 76 35 68 97 100 89 75 58 67 86 79 55 17 25 71 10 5
| 调用 | 返回值 |
|---|---|
Measure(1, 1) |
14 |
Measure(3, 5) |
75 |
Measure(2, 4) |
76 |
Pinpoint(2, 4) |
无 |
请注意,此示例并不一定代表有意义的例程调用。