← 返回题目列表

AtCoder · ahc046_a

A. 用积木滑冰

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

问题陈述

有一个溜冰场,包括 N \times N 方块。 让 (0, 0) 是左上角正方形的坐标,并且 (i, j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 以外的所有方格 N \times N 区域被封锁且无法通行。 最初,内部没有任何块 N \times N 区域。

你从初始位置开始 (i_0, j_0) 并且必须访问指定的目标方格 (i_1, j_1), \dots, (i_{M-1}, j_{M-1}) 按照给定的顺序。

在每一回合,你可以选择四个基本方向之一并执行以下操作之一:

  • 移动:向指定方向移动一格。您无法移动到包含方块的方格中。
  • 幻灯片:继续沿指定方向滑动,直到碰到方块。
  • 改变:在指定方向的相邻方块上放置一个方块(如果该方块尚不包含方块);否则,删除现有块。 您不能指定外部的正方形 N \times N 区域。 还可以在当前或未来的目标方格上放置方块;但是,您必须移除该方块才能访问该广场。

如果您滑过目标方格而不停留在其上,则它是 不 视为已访问过。 仅当您在经过一段时间后停在目标方格上时,才将其视为已访问过。 幻灯片,或直接通过 移动.

您必须按照给定的顺序访问目标方格。 即使您在访问较早的目标方格之前经过了较晚的目标方格,该方格当时也不会被视为已访问过。当序列轮到时,您将需要再次访问它。

您最多可以执行 2NM 行动。 使用尽可能少的回合,按照指定的顺序访问所有目标方格。

评分

让 T 是输出动作序列的长度,并且 m 是成功访问的目标方格的数量。 然后,您将获得以下分数。

  • If m<M-1, m+1
  • If m=M-1, M+2NM-T

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出:

N M
i_0 j_0
\vdots
i_{M-1} j_{M-1}
  • 在所有测试用例中, N = 20 和 M = 40 已修复。
  • 坐标 初始位置和每个目标方格的 (i_k, j_k) 是满足的整数 0 \leq i_k, j_k \leq N-1,并且所有坐标都是不同的。

输出

在每个回合中,使用单个大写字母表示所选的动作和方向,如下所示。

行动

  • 移动: M
  • 幻灯片: S
  • 更改: A

路线

  • 上: U
  • 向下: D
  • 左: L
  • 右: R

让 a_t 和 d_t 表示轮流选择的动作和方向 t (t = 0, 1, \dots, T-1),分别。
然后,按以下格式输出到标准输出:

a_0 d_0
\vdots
a_{T-1} d_{T-1}

显示示例

输入生成

初始位置和目标方块根据以下过程生成。

首先,随机打乱所有坐标 N^2 方块。 然后,取第一个 来自打乱列表的 M 坐标并将它们按顺序分配为 (i_0, j_0), (i_1, j_1), \dots, (i_{M-1}, j_{M-1}).

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。


示例输入 1

20 40
3 7
14 16
19 19
0 8
0 10
17 11
11 7
19 12
10 12
5 4
13 5
19 10
19 14
1 19
8 5
6 9
9 3
10 0
8 7
17 17
4 2
1 13
9 17
13 4
9 14
19 13
16 9
8 17
10 18
14 3
14 13
18 19
3 14
8 13
7 9
12 18
8 6
10 7
12 1
5 17

示例输出 1

S D
M U
A D
M U
M U
M U
M U
S R
M L
M L
M L
S D
S R
S L
S U
M R
M R