AT_s8pc_5_i.Collecting Gems is Fun

在一个炎热的夏天，E869120 来到了 AtCoder 公园。公园可以被看作一个 $H$ 行 $W$ 列的网格，其中左上角是 $(1, 1)$，右下角是 $(H, W)$。公园里有 $N$ 个宝石，它们分布在不同的格子中，没有两个宝石处于同一个格子。

E869120 决定要收集所有的宝石。他拥有一种独特的能力，能够通过预先设定的一些「相对位置」来感知是否有宝石在「附近」。例如，在下图中，如果他当前位于格子 $(4, 4)$，则可以探测到格子 $(6, 5)$ 和 $(2, 4)$ 的宝石，因为相对坐标是 $(2, 1)$ 和 $(-2, 0)$，这两者被认为是在附近。然而，位于 $(2, 3)$ 的宝石不会被判定为在附近，因为相对位置 $(-2, -1)$ 不在设定的范围之内。

E869120 从格子 $(1, 1)$ 开始移动。请你编写一个程序，利用他所能感知的信息，尽可能高效地收集所有宝石。仅使用「附近有宝石」或「没有宝石」的信息来寻找宝石。E869120 每次只能移动一格，方向可以是左、右、上、下，每次移动用时 $1$ 秒，但拾取当前位置的宝石耗时为 $0$ 秒。

输入格式

这是一个交互式题目，你的程序需要与评测系统实时通信，因此输入输出格式较为不同：

1. 首先，你需要接收公园的尺寸 $H$ 和 $W$，以及宝石的数量 $N$：

   H W N
   

2. 接下来，你需设定「附近位置」的相对坐标：

   P
   x_1 y_1
   x_2 y_2
   ...
   x_P y_P
   

   其中，第一行是「附近位置」的数量 $P$，满足 $0 \leq P \leq 500$。之后的 $P$ 行分别为每个相对位置的坐标 $(x_i, y_i)$，要求 $|x_i|, |y_i| \leq 10^9$，不能为 $(0, 0)$。

然后，在如下步骤中反复进行：

1. 系统给出状态信息：

   S
   

   • far: 当前格子和设定的「附近位置」都没有宝石。
   • close: 当前格子没有，但「附近位置」有宝石。
   • get-far: 当前格子有宝石，取走后，「附近位置」没有宝石。
   • get-close: 当前格子有宝石，取走后，「附近位置」仍有宝石。
   • get-clear: 当前格子上的宝石被取走，并且这是最后一个宝石，此信息出现后程序应立即终止。

2. 你需输出 E869120 的移动方向：

   c
   

   • L 表示向左移动一格
   • R 表示向右移动一格
   • U 表示向上移动一格
   • D 表示向下移动一格

注意不可移出网格边界且每次输出后需刷新缓冲区，避免超时。总移动次数不能超过 $10000$ 次。

数据范围与提示

• $ H = 100 $
• $ W = 100 $
• $ N = 200 $

公园内宝石的位置，是在 $10000$ 个格子中随机选出 $200$ 个位置。

得分规则

每个测试案例满分为 $100$，根据移动次数 $L$ 计算得分：

• $ L \leq 2100 $ 时，得 $100$ 分。
• $ 2101 \leq L \leq 2260 $ 时，得分为 $ \lfloor 100 - \frac{L - 2100}{8} \rfloor $。
• $ 2261 \leq L \leq 2540 $ 时，得分为 $ \lfloor 80 - \frac{L - 2260}{14} \rfloor $。
• $ 2541 \leq L \leq 3000 $ 时，得分为 $ \lfloor 60 - \frac{L - 2540}{25} \rfloor $。
• $ 3001 \leq L \leq 5000 $ 时，得分为 $ \lfloor 41.6 - \frac{L - 3000}{125} \rfloor $。
• $ 5001 \leq L \leq 6000 $ 时，得 24 分。
• $ 6001 \leq L \leq 7000 $ 时，得 21 分。
• $ 7001 \leq L \leq 8000 $ 时，得 18 分。
• $ 8001 \leq L \leq 9000 $ 时，得 15 分。
• $ 9001 \leq L \leq 10000 $ 时，得 3 分。

以下是移动次数和得分关系的图示：

示例

下图展示了一个公园的样例状态和选择的「附近位置」（即 8 邻居）的情况：

一个可能的交互示例过程如下：

初始输入为 H, W, N 的值：

4 4 4

设定「附近位置」：

8
-1 -1
-1 0
-1 1
0 -1
0 1
1 -1
1 0
1 1

随后的交互过程可能是：

get-far
R
close
D
close
D
get-close
R
close
U
get-close
U
get-clear

这表示初始在 $(1, 1)$，通过一系列判断和移动后，E869120 成功收集了所有宝石。

本翻译由 AI 自动生成