故事
高桥喜欢拼图,正在玩以下著名的滑动拼图。
有 N^2-1 上的瓷砖 N \times N 板。 有一个空方块,您可以将四个方向中任何一个方向的相邻图块滑入空方块中。 有些图片被分成每个图块。通过反复滑动瓷砖,请对齐图片。
麻烦的是,高桥扔掉了说明书,所以他丢失了目标图片。 根据他的记忆,目标图片是一张 树。 通过重复滑动操作,请完成一棵树。
问题陈述
有 N^2-1 上的瓷砖 N \times N 板。 让 (i, j) 表示行的坐标 i (0\leq i \leq N-1) 从顶部和列 j (0\leq j\leq N-1) 从左边开始。 每个图块包含一个图形,其线条从其中心朝向四个方向中的一个或多个方向:上、下、左、右。 我们使用位掩码来表示每个图块,其中 1 代表左,2 代表上,4 代表右,8 代表下,如下所示。
| 瓷砖 | ||||||||||||||||
| 二进制 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 十六进制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
数字0代表一个空方格,并且正好有一个空方格。 通过一次操作,您可以将与空方格相邻的一块图块向四个方向滑动到空方格的位置。移动后,移动棋子的方格将变成空方格。 最多可以重复滑动操作 T=2\times N^3 次。
完成操作后,考虑一个图表 N^2-1 除空方格以外的方格作为顶点和下面的边。
- 对于每个 (i, j) (0\leq i\leq N-2, 0\leq j\leq N-1),如果 (i,j) 是一个带有向下线的图块,并且 (i+1,j) 是一个具有向上线的图块,然后在之间构建一条边 (i,j) 和 (i+1,j).
- 对于每个 (i, j) (0\leq i\leq N-1, 0\leq j\leq N-2),如果 (i,j) 是一个带有向右线的图块, (i,j+1) 是一个带有向左线的图块,然后在之间构建一条边 (i,j) 和 (i,j+1).
你的任务是找到一个短的操作序列,使得该图中最大树的大小(即没有环路的最大连通分量的顶点数)尽可能大。 保证在 T 操作可以构造一个大小的树 N^2-1 中的空方块 (N-1,N-1)。 请注意,空方块的最终位置是任意的,您不必将其移动到 (N-1,N-1).
评分
让 K 是操作次数并且 S 是应用操作序列后画在板上的最大树的大小。 然后,您将得到以下分数。
- If S<N^2-1, \mathrm{round}\left(500000\times \frac{S}{N^2-1}\right)
- If S=N^2-1, \mathrm{round}\left(500000\times (2-\frac{K}{T})\right)
如果操作次数超过 T 或者您执行非法操作将不存在的图块移至空方格,将被判定为 WA .
测试用例数量
- 临时测试:50
- 系统测试:3000。我们将发布 种子.txt (sha256=041256f962c6ba1a60294ad7a575684d6e401163cba316cf978f2e66a4f7b0e3) 比赛结束后。
- 临时测试和系统测试都包含相同数量的输入 N=6,7,8,9,10.
提交的分数是每个测试用例的总分。 在临时测试中,如果您的提交产生非法输出或某些测试用例超出时间限制,则提交本身将被判定为 WA or TLE ,提交的分数将为零。 在系统测试中,如果您提交的测试用例产生非法输出或超出时间限制,则只有这些测试用例的分数为零。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在 s 系统测试。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入
输入由标准输入按以下格式给出:
N T
t_{0,0} \cdots t_{0,N-1}
\vdots
t_{N-1,0} \cdots t_{N-1,N-1}
N 是代表棋盘高度和宽度的整数,满足 6\leq N\leq 10。
在所有测试用例中, T=2\times N^3.
t_{i,0} \cdots t_{i,N-1} 是一个长度为的字符串 N。
的 j- 第一个字符 t_{i,j} is 0-9 or a-f 这是图块中包含的数字的十六进制表示 (i,j).
输出
通过单个字符来表示将向上、向下、向左或向右相邻的图块滑入空方格的每个操作 U, D, L or R分别输出序列 K 作为长度字符串进行操作 K 在一行中连接到标准输出。
输入生成
的一代 N 和 T
我们生成 N 作为种子值除以 5 + 6 的余数。 因此,您可以生成具有特定的输入 N 值通过调整种子值来实现。 我们设定 T=2\times N^3.
的一代 t_{i,j}
让 [k]=\{0,1,\cdots,k-1\}。 我们随机生成一棵生成树 (V,F) 带有顶点 V=[N]\times [N]\setminus \{(N-1,N-1)\} 如下。
- 首先,我们随机打乱边缘 \{\{(i,j),(i+1,j)\}\mid (i,j)\in [N-1]\times [N]\setminus \{(N-2,N-1)\}\}\cup\{\{(i,j),(i,j+1)\}\mid (i,j)\in [N]\times [N-1]\setminus \{(N-1,N-2)\}\} 并获得有序边列表 e_0, e_1, \cdots.
- 从 F=\emptyset,对于每个 e_k=\{(i,j),(i',j')\},我们插入 e_k 进入 F if (i,j) 和 (i',j') 未连接 (V,F).
从获得的生成树中,我们构建了图块,其上的树大小为 N^2-1 绘制如下。
- 对于每个 (i,j),如果 \{(i,j),(i+1,j)\}\in F,然后在图块上画一条向下的线 (i, j) 和瓷砖上的向上线 (i+1,j).
- 对于每个 (i,j),如果 \{(i,j),(i,j+1)\}\in F,然后在图块上画一条向右的线 (i, j) 和图块上的向左线 (i,j+1).
最后,从构造好的tile布局开始,随机执行 T=2\times N^3 滑动操作,并让 t 是操作后的图块布局。 在这里, k (\geq 2)-th 操作是从最多三个方向均匀随机选择的,不包括恢复操作的方向 (k-1)-第次操作。
工具(输入生成器和可视化工具)
- 网页版:这个比本地版本更强大,可以显示动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
比赛期间,您可以在 Twitter 上分享提供的 Seed=0 可视化工具的输出图像 (PNG)。 请注意,禁止以视频格式共享。 您必须使用指定的主题标签和公共帐户。 您只能共享seed=0 的可视化结果和分数。 请勿分享 GIF、输出本身、其他种子的分数或提及解决方案或讨论。 (已添加)可视化工具具有更改 N 值的功能,但也禁止共享已更改输入的可视化结果。
示例输入 1
6 432 62ce43 a068f9 a89da9 5d93cb 276253 424ba8
示例输出 1
RRRDLUULDDDDLUUUR