UOJ Logo Universal Online Judge

UOJ

#798. 【NOI 春季测试 2023】密码锁

附件下载 统计

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

小 I 自行车上的密码锁有 n 个拨圈,每个拨圈有 kk4)格。密码锁上的每一格都包含一个正整数,其中第 j 个拨圈的第 i 格上的正整数为 ai,j

day1_Page_11_Image_0001.jpg

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

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

day1_Page_11_Image_0002.jpg

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

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

c(i)=maxj=1nai,jminj=1nai,j

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

C=max1ikc(i)

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

输入格式

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

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

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

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

接下来 k 行,每行包含 n 个正整数,其中第 i 行第 j 个整数 ai,j 表示密码锁第 j 个拨圈上第 i 格对应的数字。

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

输出格式

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

样例一

input

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

output

0
1

explanation

第一组样例对应题目描述中的例子。

在拨第二个拨圈一次后,每个拨圈都是 {1,2,3},此时松散度为 0

容易证明无论如何松散度都不可能小于 0,因此输出 0

样例二

见下发文件。

本样例中 k=1

样例三

见下发文件。

本样例中 k=2

样例四

见下发文件。

本样例中 k=3

样例五

见下发文件。

本样例中 k=4

子任务

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

对于所有数据,保证 1T1k41ai,j3×104

本题分为两类测试点。

第一类测试点共有十二个,保证 k3n5×104n1.5×105

测试点编号 n n k=
1 20 100 1
2 5×104 1.5×105
3 20 100 2
4 100 1000
5 2000 104
6 5×104 1.5×105
7 10 50 3
8 50 500
9 300 3000
10 3000 2×104
11 3×104 1.2×105
12 5×104 1.5×105

第二类测试点共有八个,保证 k=4n104n3×104

测试点编号 n n k=
13 10 50 4
14 50 500
15 200 2000
16 500 4000
17 2500 104
18 5000 2×104
19 104 3×104
20 104 3×104

时间限制:2.5s3.5s

空间限制:1GB

后记

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