CF1236C Labs

为了进行一些研究，在一座山的不同高度上建造了 $n^2$ 个实验室。我们用整数 $1$ 到 $n^2$ 对这些实验室进行编号，其中编号为 $1$ 的实验室位于最低处，编号为 $2$ 的实验室位于第二低处，依此类推，编号为 $n^2$ 的实验室位于最高处。 为了在实验室之间运输水，每对实验室之间都建立了一根管道。如果 $u > v$，则一根管道可以在编号为 $u$ 的实验室和编号为 $v$ 的实验室之间一次最多运输一单位水。 现在需要将这些实验室分成 $n$ 个组，每组恰好包含 $n$ 个实验室。不同组之间的实验室可以相互运输水。从组 $A$ 向组 $B$ 能运输的水的总单位数，等于满足编号为 $u$ 的实验室属于组 $A$，编号为 $v$ 的实验室属于组 $B$，且 $u > v$ 的所有实验室对 $(u, v)$ 的数量。我们用 $f(A,B)$ 表示该值（即 $f(A,B)$ 是从组 $A$ 向组 $B$ 能运输的水的总单位数）。 例如，当 $n=3$ 时，有 $3$ 个组 $X$、$Y$ 和 $Z$：$X = \{1, 5, 6\}$，$Y = \{2, 4, 9\}$，$Z = \{3, 7, 8\}$。此时，各组之间的 $f$ 值如下： - $f(X, Y) = 4$，因为有 $5 \rightarrow 2$，$5 \rightarrow 4$，$6 \rightarrow 2$，$6 \rightarrow 4$； - $f(X, Z) = 2$，因为有 $5 \rightarrow 3$，$6 \rightarrow 3$； - $f(Y, X) = 5$，因为有 $2 \rightarrow 1$，$4 \rightarrow 1$，$9 \rightarrow 1$，$9 \rightarrow 5$，$9 \rightarrow 6$； - $f(Y, Z) = 4$，因为有 $4 \rightarrow 3$，$9 \rightarrow 3$，$9 \rightarrow 7$，$9 \rightarrow 8$； - $f(Z, X) = 7$，因为有 $3 \rightarrow 1$，$7 \rightarrow 1$，$7 \rightarrow 5$，$7 \rightarrow 6$，$8 \rightarrow 1$，$8 \rightarrow 5$，$8 \rightarrow 6$； - $f(Z, Y) = 5$，因为有 $3 \rightarrow 2$，$7 \rightarrow 2$，$7 \rightarrow 4$，$8 \rightarrow 2$，$8 \rightarrow 4$。 请将实验室分成 $n$ 个组，每组大小为 $n$，使得所有不同组对 $A$ 和 $B$（$A \neq B$）的 $f(A,B)$ 的最小值最大。 换句话说，请将实验室分成 $n$ 个组，每组大小为 $n$，使得对于每一对不同的组 $A$ 和 $B$（$A \neq B$），从组 $A$ 向组 $B$ 能运输的水的总单位数的最小值尽可能大。 注意，上述例子并不是最优划分，只是展示了如何计算某种划分下的 $f$ 值。 如果存在多种最优划分方案，你可以输出任意一种。

一行包含一个整数 $n$（$2 \leq n \leq 300$）。

输出 $n$ 行： 第 $i$ 行输出 $n$ 个整数，表示第 $i$ 个组中实验室的编号，顺序任意。 如果存在多种最优方案，使得从一个组向另一个组能运输的水的总单位数的最小值最大，你可以输出任意一种。

在第一个测试样例中，可以将 $9$ 个实验室分为 $\{2, 8, 5\}, \{9, 3, 4\}, \{7, 6, 1\}$ 三组。 从第一组到第二组可以运输 $4$ 单位水（$8 \rightarrow 3, 8 \rightarrow 4, 5 \rightarrow 3, 5 \rightarrow 4$）。 从第一组到第三组可以运输 $5$ 单位水（$2 \rightarrow 1, 8 \rightarrow 7, 8 \rightarrow 6, 8 \rightarrow 1, 5 \rightarrow 1$）。 从第二组到第一组可以运输 $5$ 单位水（$9 \rightarrow 2, 9 \rightarrow 8, 9 \rightarrow 5, 3 \rightarrow 2, 4 \rightarrow 2$）。 从第二组到第三组可以运输 $5$ 单位水（$9 \rightarrow 7, 9 \rightarrow 6, 9 \rightarrow 1, 3 \rightarrow 1, 4 \rightarrow 1$）。 从第三组到第一组可以运输 $4$ 单位水（$7 \rightarrow 2, 7 \rightarrow 5, 6 \rightarrow 2, 6 \rightarrow 5$）。 从第三组到第二组可以运输 $4$ 单位水（$7 \rightarrow 3, 7 \rightarrow 4, 6 \rightarrow 3, 6 \rightarrow 4$）。 从一个组到另一个组能运输的水的总单位数的最小值为 $4$。可以证明无法得到更优的划分。 由 ChatGPT 4.1 翻译