← 返回题目列表

AtCoder · masters_qual_a

A. 通过交换进行平滑

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

问题陈述

有一个 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 步骤。

  1. 如果愿意的话,高桥和青木当前位置上的数字可以交换。
  2. 如果高桥愿意,他可以移动到与当前位置相邻的方格。
  3. 如果 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 是表示高桥移动方向的字符, U D L R 分别向上、下、左、右移动到相邻的方格,或者 . 如果他没有移动并停留在当前位置。
  • 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.

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

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


示例输入 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