← 返回题目列表

Codeforces · 1521/E

E. 娜斯蒂亚和美丽的矩阵

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

你喜欢数字,不是吗? Nastia 有很多数字,她想与您分享!是不是很神奇呢?

设 $$$a_i$$$ 为你有多少个数字 $$$i$$$ ($$$1 \le i \le k$$$)。

如果 $$$n \times n$$$ 矩阵包含您拥有的所有数字,并且对于每个 $$$2 \times 2$$$ 原始矩阵的子矩阵都满足:

1. 占用单元格数量不超过$$$3$$$;
2. 每条对角线上的数字不同。

制作一个最小尺寸的漂亮矩阵。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。

每个测试用例的第一行包含 $$$2$$$ 整数 $$$m$$$ 和 $$$k$$$ ($$$1 \le m, k \le 10^5$$$) – Nastia 分别给了你多少个数字和数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_{k}$$$ ($$$0 \le a_i \le m$$$, $$$a_1 + a_2 + \ldots + a_{k} = m$$$),其中 $$$a_i$$$ 是多少个数字$$$i$$$ 你有。

保证一次测试中 $$$m$$$ 和 $$$k$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个 $$$t$$$ 测试用例,打印一个整数 $$$n$$$ — 美丽矩阵的大小。

在接下来的 $$$n$$$ 行中,打印 $$$n$$$ 整数 $$$b_{i, j}$$$ ($$$0 \le b_{i, j} \le k$$$; 如果位置为空,则打印 $$$b_{i, j} = 0$$$) — 您组成的漂亮矩阵 $$$b$$$。

示例

输入 #1

2
3 4
2 0 0 1
15 4
2 4 8 1

输出 #1

2
4 1
0 1
5
3 0 0 2 2
3 2 3 3 0
0 1 0 4 0
3 0 0 0 0
2 1 3 3 3

注意

请注意,此问题中的 $$$0$$$ 代表空格,而不是数字。

第一个测试用例的可能答案示例:

$$$\begin{array}{cc} 1 & 1 \\ 4 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 4 \\ 1 & 0 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 0 \\ 1 & 1 \\ \end{array}$$$

第一个测试用例的不漂亮矩阵示例:

$$$\begin{array}{cc} 1 & 0 \\ 4 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 1 \\ 7 & 1 \\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 0 \\ 4 & 0 \\ \end{array}$$$

第二个测试用例的不漂亮矩阵的示例:

$$$\begin{array}{cc} 3 & 4 & 0 & 2 & 2 \\ 3 & 2 & 3 & 3 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 \\ 2 & 1 & 3 & 3 & 3 \\ \end{数组}$$$

一切都很好,除了左上角的子矩阵包含 $$$4$$$ 数字。