← 返回题目列表

Codeforces · 1956/C

C. 内内的魔法矩阵

中文机器翻译题面 查看原题

魔法少女 Nene 有一个用零填充的 $$$n\times n$$$ 矩阵 $$$a$$$。矩阵$$$a$$$第$$$i$$$行的第$$$j$$$元素表示为$$$a_{i, j}$$$。

她可以用这个矩阵执行以下两种类型的运算:

- 输入 $$$1$$$ 操作:选择 $$$1$$$ 和 $$$n$$$ 之间的整数 $$$i$$$ 以及从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1, p_2, \ldots, p_n$$$。同时为所有 $$$1 \le j \le n$$$ 分配 $$$a_{i, j}:=p_j$$$。
- 输入 $$$2$$$ 操作:选择 $$$1$$$ 和 $$$n$$$ 之间的整数 $$$i$$$ 以及从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1, p_2, \ldots, p_n$$$。同时为所有 $$$1 \le j \le n$$$ 分配 $$$a_{j, i}:=p_j$$$。

Nene 想要最大化矩阵 $$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$$$ 中所有数字的总和。她要求你找到执行运算的方法,以使这个总和最大化。由于她不想进行太多操作,因此您应该提供一个不超过 $$$2n$$$ 操作的解决方案。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数以任意顺序组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 矩阵 $$$a$$$ 的大小。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,在第一行输出两个整数 $$$s$$$ 和 $$$m$$$ ($$$0\leq m\leq 2n$$$) - 矩阵中的数字与解决方案中的操作数的最大总和。

在接下来的 $$$m$$$ 行的第 $$$k$$$ 行中输出第 $$$k$$$ 操作的描述:

- 整数 $$$c$$$ ($$$c \in \{1, 2\}$$$) — 第 $$$k$$$ 操作的类型;
- 整数 $$$i$$$ ($$$1 \le i \le n$$$) - 第 $$$k$$$ 操作应用到的行或列;
- 从 $$$1$$$ 到 $$$n$$$ 的整数的排列 $$$p_1, p_2, \ldots, p_n$$$ - 第 $$$k$$$ 操作中使用的排列。

请注意,您不需要最小化所使用的操作数量,您只应该使用不超过 $$$2n$$$ 操作。可以证明,总是可以在不超过 $$$2n$$$ 操作中获得最大可能的总和。

示例

输入 #1

2
1
2

输出 #1

1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

注意

在第一个测试用例中,通过设置$$$a_{1, 1}:=1$$$,可以在$$$1$$$操作中获得最大和$$$s=1$$$。

在第二个测试用例中,可以通过$$$3$$$操作获得最大和$$$s=7$$$,如下所示:

可以证明,不可能使矩阵中的数字之和大于$$$7$$$。