#1561. [语言月赛202210] 军训

[语言月赛202210] 军训

题目描述

某 E 刚结束军训,军训教官将所有同学排成了 nn 行 mm 列。

教官组织同学们进行分列式练习,同学们将按行为单位进行练习。第 ii 行第 jj 名同学摆臂的高度为 ai,ja_{i,j},踢腿的高度为 bi,jb_{i,j}。

教官认为,每一行同学的不整齐度为摆臂高度方差与踢腿高度方差之和。形式化的,第 ii 行同学的不整齐度为

$$\dfrac{1}{m} \times \sum\limits_{j=1}^{m}{\Bigg(a_{i,j}-\dfrac{\sum\limits_{k=1}^{m}{a_{i,k}}}{m}\Bigg)^2} + \dfrac{1}{m} \times \sum\limits_{j=1}^{m}{\Bigg(b_{i,j}-\dfrac{\sum\limits_{k=1}^{m}{b_{i,k}}}{m}\Bigg)^2}$$

其中,∑j=1mai,j\sum\limits_{j=1}^m{a_{i,j}} 代表 ai,1+ai,2+ai,3+⋯+ai,ma_{i,1}+a_{i,2}+a_{i,3}+\cdots+a_{i,m}。

教官希望对若干行进行位置上的对调,使得最终排出的方阵中,从第 11 行至第 nn 行不整齐度依次递增。若有两行不整齐度相同,可以任意安排其顺序。

请你编写程序,给出一种交换方案。请注意,每一步交换是即刻完成的。

例如,给出如下的交换方案:

第一步,交换第 11 行和第 22 行;第二步,交换第 22 行和第 33 行。

初始:

当前行数 初始行号
11
22
33

第一步完成后:

当前行数 初始行号
11 22
22 11
33

第二步完成后:

当前行数 初始行号
11 22
22 33
33 11

提示:例如,将第 11 行与第 33 行交换后,原第 11 行将被叫做第 33 行,而不是仍被叫做第 11 行。

具体解释可参照样例 #2 解释。

输入格式

输入共 2n+12n+1 行。

输入的第一行为两个整数 m,nm,n,分别代表列数和行数。

接下来 nn 行,每行 mm 个整数,第 ii 行第 jj 个代表 ai,ja_{i,j}。

接下来 nn 行,每行 mm 个整数,第 ii 行第 jj 个代表 bi,jb_{i,j}。

输出格式

输出若干行。

输出的第一行为一个整数 KK,代表你交换方案中交换的次数。

接下来 KK 行,每行输出两个整数 x,yx,y,代表将第 xx 行与第 yy 行的同学进行交换。

注意:KK 应当不超过 n2n^2。

样例

3 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
3
1 2
1 3
2 3
3 3
3 6 9
2 4 6
1 2 3
1 1 1
1 1 1
1 1 1
3
1 2
2 3
1 2

题目来源:洛谷 B3675