#NOISC2023D. 密码锁

密码锁

题目描述

寒假过后,小 I 回到学校,发现自己忘记了自行车锁的密码,于是请你帮忙。

小 I 自行车上的密码锁有 nn 个拨圈,每个拨圈有 kkk4k \leq 4)格。密码锁上的每一格都包含一个正整数,其中第 jj 个拨圈的第 ii 格上的正整数为 ai,ja _ {i, j}

(一个锁的例子,其中 k=n=3k = n = 3,每列表示一个拨圈,拨圈的格子从上往下编号。)

你可以对每个拨圈拨若干次(也可以不拨),每拨一次拨圈,它的格子就会进行一次轮换。形式化地,拨第 jj 个拨圈一次,则会让第 jj 个拨圈上第 ii 格的数字移动到第 ((imodk)+1)((i \bmod k) + 1) 格,其他拨圈不动。

(一个拨动拨圈的例子,对左侧的锁拨一次第二个拨圈得到右侧的锁。)

为了方便记忆,小 I 设定密码时要求同一行上的数字尽可能靠近。 形式化地,对于 1ik1 \leq i \leq k,定义密码锁第 ii 行的松散度为

$$c(i) = \max \limits _ {j = 1} ^ n a _ {i, j} - \min \limits _ {j = 1} ^ n a _ {i, j} $$

同时定义整个密码锁的松散度为

C=max1ikc(i)C = \max \limits _ {1 \leq i \leq k} c(i)

因为能开锁的状态满足 CC 尽可能小,因此小 I 希望你找出最小的 CC 值。

输入格式

本题有多组测试数据,题目保证一个测试点中所有测试数据的 kk 相同。

第一行包含两个正整数 T,kT, k,分别表示测试数据组数和密码锁拨圈上的格数。

接下来一共 TT 组数据,每组数据格式如下:

第一行包含一个正整数 nn,表示拨圈数。

接下来 kk 行,每行包含 nn 个正整数,其中第 ii 行第 jj 个整数 ai,ja _ {i,j} 表示密码锁第 jj 个拨圈上第 ii 格对应的数字。

注意输入的矩阵中每一列对应一个拨圈,而非每一行对应一个拨圈。

输出格式

对于每组数据,输出一行包含一个整数,表示所有方案中 CC 的最小值。

样例 #1

样例输入 #1

2 3
3
1 2 1
2 3 2
3 1 3
2
1 2
2 1
1 2

样例输出 #1

0
1

样例 #2

样例输入 #2

见选手目录下的 lock/lock2.in。

样例输出 #2

见选手目录下的 lock/lock2.ans。

样例 #3

样例输入 #3

见选手目录下的 lock/lock3.in。

样例输出 #3

见选手目录下的 lock/lock3.ans。

样例 #4

样例输入 #4

见选手目录下的 lock/lock4.in。

样例输出 #4

见选手目录下的 lock/lock4.ans。

样例 #5

样例输入 #5

见选手目录下的 lock/lock5.in。

样例输出 #5

见选手目录下的 lock/lock5.ans。

提示

【样例 1 解释】

第一组样例对应题目描述中的例子。 在拨第二个拨圈一次后,每个拨圈都是 {1,2,3}\{1, 2, 3\},此时松散度为 00。 容易证明无论如何松散度都不可能小于 00,因此输出 00

以下四个样例分别对应 k=1,2,3,4k = 1, 2, 3, 4 的情况,且样例中 nn 的取值有一定梯度。

【数据范围】

n\sum n 为一个测试点中所有测试数据的 nn 的和。

对于所有数据,保证 1T1 \leq T1k41 \leq k \leq 41ai,j3×1041 \leq a _ {i ,j} \leq 3 \times 10 ^ 4

本题分为两类测试点。

第一类测试点共有十二个,保证 k3k \leq 3n5×104n \leq 5 \times 10 ^ 4n1.5×105\sum n \leq 1.5 \times 10 ^ 5

测试点编号 nn \leq n\sum n \leq k=k =
11 2020 100100 11
22 5×1045 \times 10 ^ 4 1.5×1051.5 \times 10 ^ 5
33 2020 100100 22
44 100100 10001000
55 20002000 10410 ^ 4
66 5×1045 \times 10 ^ 4 1.5×1051.5 \times 10 ^ 5
77 1010 5050 33
88 5050 500500
99 300300 30003000
1010 30003000 2×1042 \times 10 ^ 4
1111 3×1043 \times 10 ^ 4 1.2×1051.2 \times 10 ^ 5
1212 5×1045 \times 10 ^ 4 1.5×1051.5 \times 10 ^ 5

第二类测试点共有八个,保证 k=4k = 4n104n \leq 10 ^ 4n3×104\sum n \leq 3 \times 10 ^ 4

测试点编号 nn \leq n\sum n \leq k=k =
1313 1010 5050 44
1414 5050 500500
1515 200200 20002000
1616 500500 40004000
1717 25002500 10410 ^ 4
1818 50005000 2×1042 \times 10 ^ 4
1919 10410 ^ 4 3×1043 \times 10 ^ 4
2020

【后记】

你花了九牛二虎之力算出 CC 的值之后,小 I 却告诉你他已经找开锁师傅用锤子暴力破解了。在你的百般劝说下,小 I 承诺以后锁车不用有大于等于一万个拨圈的密码锁。