最高分数: 1500 点
问题陈述
有一天,编码员E869120去了“AtCoder自然公园”。
公园表示为 H*W 网格。左上角的单元格是 (1,1) 右下角单元格是 (H,W).
此外, N 宝石掉落在公园里。每个单元格中不超过 1 宝石掉落。
他想收集公园里的所有宝石。
他有“特殊的嗅觉”,所以如果有 1 或者更多他事先决定的相对位置的宝石,他认为“我附近有一颗宝石”。
“相对位置”示例如下:
左图中,如果单元格中存在E869120 (4, 4),单元格中的宝石 (6, 5) 和 (2, 4) 是“附近”。假设他的相对位置是 (0, 0)。在这种情况下,示例中 gem 的相对位置为 (2, 1) 和 (-2, 0) 按顺序。要看图片,两个 (2, 1) 和 (-2, 0) 就在附近。
但是 (2, 3) 不近,因为它的相对位置是 (-2, -1) 只要看图片就不是很近。
但是,他可以移动到共享一侧的 4 个相邻单元格之一 1 第二。如果单元格上有 E869120 存在的宝石,他会自动选择它 0 第二。
最初,他在牢房里 (1, 1)。请尽快编写收集公园内所有宝石的程序。
输入和输出
这个问题是“交互式任务”(必须与程序的输入和输出进行通信的任务),因此输入/输出的格式很特殊。
首先,给出“AtCoder Natural Park”的大小: H 和 W。您还会获得宝石数量: N。输入格式如下:
H W N
其次,必须设置包含“近”的相对方向,使E869120具有“特殊的嗅觉”。
P x_1 y_1 x_2 y_2 ... x_P y_P
在 1-st 行,您应该输出包含“near”的相对位置数: P. 0 \leq P \leq 500 应该满足。
从 2-nd 行 P+1-第行,您应该输出相对位置: (x_i, y_i). x_i,y_i 应大于 -10^9 且小于 10^9. 如果E869120存在的单元格上有宝石,他会立即拾取它。所以, (x_i, y_i) 不应该 (0, 0).
接下来,交替重复以下两个过程(☆)和(★)(第一个过程是(☆))。
(☆) 您得到的信息如下:
S
信息分类如下:
far:他的牢房里没有宝石。另外,您设置的相对位置中没有宝石。close:他的牢房里没有宝石。此外,还有 1 或更多处于您设置的相对位置的宝石。get-far:他的细胞里有一颗宝石,所以E869120选择了它。另外,他采摘后你设置的宝石的相对位置也没有。get-close:他的细胞里有一颗宝石,所以E869120选择了它。此外,还有 1 或更多宝石,其相对位置是您在他挑选后设置的。get-clear:他的细胞里有一颗宝石,所以E869120选择了它。此外,收集所有宝石。如果给定您的程序,您必须终止您的程序get-clear.
(★) E869120 移动。您应该打印如下:
c
- If c is
L,这意味着他移到了左边的单元格。 - If c is
R,这意味着他移动到了右边的单元格。 - If c is
U,这意味着他移动到了上面的单元格。 - If c is
D,这意味着他移动到了下方的单元格。 - 他不应该搬到公园外面。
注意
如果您的输出格式无效或者他移出公园,则判决未定义。 (这意味着它不一定得到 WA)
而且,您必须刷新标准输出。
E869120 移动不应超过 10 \ 000 次。
约束
- H = 100
- W = 100
- N = 200
- 测试用例是随机生成的。
评分
有 15 此问题中的测试用例。对于每种情况,最大分数是 100 点。
让 L 是移动次数。该点的计算方式如下:
- If L \leq 2 \ 100, 100 点。
- If 2 \ 101 \leq L \leq 2 \ 260, floor(100 - \frac{L - 2100}{8}) 点。
- If 2 \ 261 \leq L \leq 2 \ 540, floor(80 - \frac{L - 2260}{14}) 点。
- If 2 \ 541 \leq L \leq 3 \ 000, floor(60 - \frac{L - 2540}{25}) 点。
- If 3 \ 001 \leq L \leq 5 \ 000, floor(41.6 - \frac{L - 3000}{125}) 点。
- If 5 \ 001 \leq L \leq 6 \ 000, 24 点。
- If 6 \ 001 \leq L \leq 7 \ 000, 21 点。
- If 7 \ 001 \leq L \leq 8 \ 000, 18 点。
- If 8 \ 001 \leq L \leq 9 \ 000, 15 点。
- If 9 \ 001 \leq L \leq 10 \ 000, 3 点。
表示移动次数与得分之间相关性的图表如下:
示例输入和输出
公园的状态以及包含“近”的相对方向如下:
计算机与法官交互如下:
| 输入 | 输出 | 留言 |
|---|---|---|
| 4 4 4 | 输入H、W、N的值。 | |
|
8 -1 -1 -1 0 -1 1 0 -1 0 1 1 -1 1 0 1 1 |
输入相对方向。 | |
| 走远 | 目前他是 (1, 1)。获得一颗宝石。 | |
| R | 移至 (1, 2)。 | |
| 关闭 | (2, 3) 中的宝石就在附近。 | |
| D | 移至 (2, 2)。 | |
| 关闭 | (2, 3) 和 (3, 2) 中的宝石很近。 | |
| D | 移至 (3, 2)。 | |
| 靠近 | 在 (3, 2) 中获得宝石。 (2, 3) 中的一颗宝石仍然很近。 | |
| R | 移至 (3, 3)。 | |
| 关闭 | (2, 3) 和 (2, 4) 中的宝石很近。 | |
| U | 移至 (2, 3)。 | |
| 靠近 | 在 (2, 3) 中获得宝石。 (2, 4) 中的一颗宝石还很近。 | |
| U | 移至 (2, 4)。 | |
| 搞清楚 | 在 (2, 4) 中获得宝石。收集所有宝石。 |