UOJ Logo Universal Online Judge

UOJ

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

附件下载 统计

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

小 I 自行车上的密码锁有 $n$ 个拨圈,每个拨圈有 $k$($k \leq 4$)格。密码锁上的每一格都包含一个正整数,其中第 $j$ 个拨圈的第 $i$ 格上的正整数为 $a _ {i, j}$。

day1_Page_11_Image_0001.jpg

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

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

day1_Page_11_Image_0002.jpg

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

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

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

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

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

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

输入格式

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

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

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

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

接下来 $k$ 行,每行包含 $n$ 个正整数,其中第 $i$ 行第 $j$ 个整数 $a _ {i,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$。

子任务

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

对于所有数据,保证 $1 \leq T$,$1 \leq k \leq 4$,$1 \leq a _ {i ,j} \leq 3 \times 10 ^ 4$。

本题分为两类测试点。

第一类测试点共有十二个,保证 $k \leq 3$,$n \leq 5 \times 10 ^ 4$,$\sum n \leq 1.5 \times 10 ^ 5$。

测试点编号 $n \leq$ $\sum n \leq $ $k = $
$1$ $20$ $100$ $1$
$2$ $5 \times 10 ^ 4$ $1.5 \times 10 ^ 5$
$3$ $20$ $100$ $2$
$4$ $100$ $1000$
$5$ $2000$ $10 ^ 4$
$6$ $5 \times 10 ^ 4$ $1.5 \times 10 ^ 5$
$7$ $10$ $50$ $3$
$8$ $50$ $500$
$9$ $300$ $3000$
$10$ $3000$ $2 \times 10 ^ 4$
$11$ $3 \times 10 ^ 4$ $1.2 \times 10 ^ 5$
$12$ $5 \times 10 ^ 4$ $1.5 \times 10 ^ 5$

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

测试点编号 $n \leq$ $\sum n \leq $ $k = $
$13$ $10$ $50$ $4$
$14$ $50$ $500$
$15$ $200$ $2000$
$16$ $500$ $4000$
$17$ $2500$ $10 ^ 4$
$18$ $5000$ $2 \times 10 ^ 4$
$19$ $10 ^ 4$ $3 \times 10 ^ 4$
$20$ $10 ^ 4$ $3 \times 10 ^ 4$

时间限制:$\require{cancel}\cancel{2.5\texttt{s}}3.5\texttt{s}$

空间限制:$\texttt{1GB}$

后记

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