← 返回题目列表

AtCoder · s8pc_5_i

I. 收集宝石很有趣

中文机器翻译题面 查看原题

最高分数: 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) 中获得宝石。收集所有宝石。