#23. 分组游戏

分组游戏

题目描述

PAFF 有一天突发奇想,想玩一个独特的数字游戏。她现在有 11 ~ n2 n^2 总共 n2n^2 个数,并且想要把这 n2n^2 个数不重不漏分为 nn 组,每组中有 nn 个数。

XXYY 为其中的两组,f(X,Y)f(X,Y) 表示 XX 中任取一个数 aaYY 中任取一个数 bba>ba > b 的情况有几种。

例如当 XX={ 1,5,61,5,6 },YY={ 2,4,92,4,9 } 时:

f(X,Y)=4f(X,Y)=45>25>46>26>45>2,5>4,6>2,6>4)。

f(Y,X)=5f(Y,X)=52>14>19>19>59>62>1,4>1,9>1,9>5,9>6)。

现在 PAFF 想知道任意一种分组的方法,使这 nn 个组中任意取两个组 XXYY,并让所有的 f(X,Y)f(X,Y) 中的最小值尽可能大。

输入格式

第一行一个数表示 nnn300n \leq 300

输出格式

总共 nn 行,每行 nn 个整数,表示每组数。 答案不唯一,输出任意一种符合题意的分组方法即可。

输入输出样例

3
2 8 5
9 3 4
7 6 1

样例说明:

在第一个测试中,我们可以将 9 9 个数字分成组 {2852, 8, 5}, {9349, 3, 4}, {7617, 6, 1} 。

从第一组到第二组,答案为 4(8 > 3、8 > 4、5 > 3、5 > 4 )。

从第一组到第三组,答案为 5(2> 1、8 > 7、8 > 6、8 > 1、5 > 1 )。

从第二组到第一组,答案为 5(9 > 2、9 > 8、9 > 5、3 > 2、4 > 2 )。

从第二组到第三组,答案为 5(9 > 7、9 > 6、9 > 1、3 > 1、4 > 1 )。

从第三组到第一组,答案为 4(7 > 2、7 > 5、6 > 2、6 > 5 )。

从第三组到第二组,答案为 4( 7 > 3, 7 > 4, 6 > 3, 6 > 4 )。

可以知道答案最小值为 4 4 。可以证明,不可能做出更好的划分。

题目背景

qwq \PAFF/\PAFF/\PAFF/