#P14133. 【MX-X22-T4】「TPOI-4D」Another Matrix Problem

【MX-X22-T4】「TPOI-4D」Another Matrix Problem

题目描述

给定正整数 nn,你需要构造一个大小为 n×nn \times n 的矩阵,使得该矩阵满足以下条件:

  1. 每行的数字依次递增。
  2. 该矩阵恰好出现过 1n21 \sim n^2 中的所有数字。
  3. 将该矩阵黑白染色后,黑色格子上的数字之和与白色格子上的数字之和的差的绝对值最小。

矩阵黑白染色的定义:对于一个位置 (i,j)(i,j),若 i+ji+j 为偶数则该位置染为黑色,反之该位置染为白色。

输入格式

仅一行,一个正整数 nn

输出格式

第一行,一个非负整数,表示可以构造出来的最小差值。

接下来 nn 行,每行 nn 个正整数,表示你构造的矩阵。

2
0
1 3
2 4
3
1
2 3 4
5 6 7
1 8 9

提示

【样例解释 #1】

样例输出的黑色格子上的数字之和与白色格子上的数字之和的差的绝对值为 00,容易证明没有比这种构造更优的构造方案。

构造方式样例输出已给出。

【样例解释 #2】

样例输出的黑色格子上的数字之和与白色格子上的数字之和的差的绝对值为 11,容易证明没有比这种构造更优的构造方案。

构造方式样例输出已给出。

【计分方式】

每个测试点总分均为 55 分。

若你的输出格式错误,你不会得到任何分数。

若第一行你的答案正确,则你可以获得 11 分。

若你的矩阵构造方案正确,则你可以获得 33 分。

若第一行你的答案正确并且你的矩阵构造方案正确,则你可以获得额外的 11 分。

【数据范围】

id\mathrm{id} 为测试点编号。

测试点编号 n=n =
191 \sim 9 id\mathrm{id}
1010 1515
1111 1616
1212 1717
1313 1919
1414 9797
1515 101101
1616 103103
1717 19931993
1818 19971997
1919 19991999
2020 20002000

对于所有数据,保证 1n20001 \le n \le 2000