问题陈述
有一个 N\times N 方板。 让 从那里向右走 (0, 0) 是左上角正方形的坐标,并且 (i, j) 是所在正方形的坐标 i 向下平方并 j 方块。 的周长 N\times N 棋盘周围有墙壁,方格之间也可能有墙壁。 当两个共享边的正方形之间没有墙壁时,它们被定义为“相邻正方形”。于日本标准时间 13:15 添加)
每个方格 (i,j) 有一个唯一的编号 a_{(i,j)} 来自 1 to N^2。 从他们最喜欢的网格初始位置开始,高桥和青木最多执行以下动作序列 4 N^2 步骤。
- 如果愿意的话,高桥和青木当前位置上的数字可以交换。
- 如果高桥愿意,他可以移动到与当前位置相邻的方格。
- 如果 Aoki 愿意,他可以移动到与当前位置相邻的方格。
操作顺序按顺序执行 1\rightarrow 2\rightarrow 3,整个序列被视为一个步骤。 他们可能会移动到相邻的方格而不交换数字,也可能在交换数字后留在同一个方格。 他们当前的位置在同一个方格内也是可以接受的。
请确定他们的行动,以使相邻方格之间的最终数字尽可能接近。
评分
让 E 是整对相邻方格的集合,并考虑相邻方格中数字之差的平方和 \sum_{u,v\in E}(a_u-a_v)^2。 让 D' 是初始状态的平方和, D 是最终状态的平方和。 然后,您将获得以下分数。
\[ \max\left(1, \mathrm{round}\left(10^6\times \log_2\frac{D'}{D}\right)\right) \]
总共有200个测试用例, 10 对于每个 t 值如下所述,每个测试用例的分数总和就是提交的分数。
测试用例分为不同的测试集(test_t)对于每个 t 值,如果输出不正确或相应超过时间限制,则仅对测试集进行评分 0。
比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。
如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出。
t N
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0}\cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
a_{0,0} \cdots a_{0,N-1}
\vdots
a_{N-1,0} \cdots a_{N-1,N-1}
- t 是表示输入生成方法的整数,满足 0\leq t\leq 19。有关详细信息,请参阅输入生成部分。
- N 是棋盘的水平和垂直尺寸,满足 10\leq N\leq 100.
- v_{i,0}\cdots v_{i,N-2} 是一个长度为的字符串 N-1 仅包含
0和1. v_{i,j}=1 当且仅当方块之间有一堵墙 (i,j) 及其右邻居 (i,j+1). - h_{i,0}\cdots h_{i,N-1} 是一个长度为的字符串 N 仅包含
0和1. h_{i,j}=1 当且仅当方块之间有一堵墙 (i,j) 及其下邻居 (i+1,j). - 所有方格都保证彼此可达。
- a_{i,j} 表示方格中最初写入的数字 (i,j),并且满足 1\leq a_{i,j}\leq N^2.
输出
首先确定高桥的初始位置 (p_i,p_j) 和青木的初始位置 (q_i,q_j),并将它们以以下格式在单行中输出到标准输出。
p_i p_j q_i q_j
初始位置可以自由确定,只要在棋盘上即可。
让 k 是总步数。 对于每个步骤,按照以下格式输出到标准输出,以空格分隔三个字符,总共得到 k 行。
s d e
- s 是表示号码是否交换的字符,
1如果是这样并且0如果没有。 - d 是表示高桥移动方向的字符,
UDLR分别向上、下、左、右移动到相邻的方格,或者.如果他没有移动并停留在当前位置。 - e 是表示青木移动方向的字符,与高桥的情况相同。
如果他和目的地之间有墙,或者步数超过 4 N^2,提交将被判定为 WA.
输入生成
输入的部分,不包括 a,根据余数固定 t 通过将生成输入的种子值除以20得到,并且内容 in_fixed/t.txt 按原样使用。
测试用例恰好包含 10 个输入 t\in \{0,1,\cdots,19\}.
数量 每个方格中的 a_{i,j} 是通过随机打乱以下值生成的 1 to N^2.
工具(输入生成器和可视化工具)
- 源代码: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止在团队之外分享可视化结果或讨论解决方案/想法。
示例输入 1
0 10 000100001 000100001 000100001 000100000 001000010 001000010 001000010 001000000 000000000 000000000 0111111100 1100000000 0000000000 1110000000 0000000111 0000000000 0000111100 0000000000 0000000000 2 47 60 6 76 72 52 90 19 77 42 59 7 45 17 80 71 55 65 75 16 21 35 9 15 95 50 91 54 20 34 39 10 38 69 99 63 92 14 87 36 89 41 81 97 78 56 30 68 98 82 67 40 73 58 26 53 33 100 74 4 12 28 64 31 37 62 24 70 93 27 61 83 94 25 32 5 88 85 46 29 13 8 86 66 57 44 23 48 11 22 49 84 18 79 1 96 43 3 51
示例输出 1
0 0 0 1 0 . R 1 D L 0 R . 0 R . 1 R L