问题陈述
有一个溜冰场,包括 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}).
工具(输入生成器和可视化工具)
- 网页版:这比提供动画和手动播放的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果您不熟悉Rust语言环境,请改用它。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 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