CF1371D.Grid-00100

A mad scientist Dr.Jubal has made a competitive programming task. Try to solve it!

You are given integers $n,k$. Construct a grid $A$ with size $n \times n$ consisting of integers $0$ and $1$. The very important condition should be satisfied: the sum of all elements in the grid is exactly $k$. In other words, the number of $1$ in the grid is equal to $k$.

Let's define:

• $A_{i,j}$ as the integer in the $i$-th row and the $j$-th column.
• $R_i = A_{i,1}+A_{i,2}+...+A_{i,n}$ (for all $1 \le i \le n$).
• $C_j = A_{1,j}+A_{2,j}+...+A_{n,j}$ (for all $1 \le j \le n$).
• In other words, $R_i$ are row sums and $C_j$ are column sums of the grid $A$.
• For the grid $A$ let's define the value $f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ (here for an integer sequence $X$ we define $\max(X)$ as the maximum value in $X$ and $\min(X)$ as the minimum value in $X$).

Find any grid $A$, which satisfies the following condition. Among such grids find any, for which the value $f(A)$ is the minimum possible. Among such tables, you can find any.

一位疯狂的科学家朱巴尔博士设计了一道编程竞赛题目。快来解决它吧！

给定整数 $n$ 和 $k$。请构造一个大小为 $n \times n$ 的网格 $A$，其中每个元素均为 $0$ 或 $1$，并严格满足：网格中所有元素之和恰好为 $k$。换言之，网格中 $1$ 的个数必须等于 $k$。

我们定义：

• $A_{i,j}$ 表示第 $i$ 行、第 $j$ 列处的整数；
• $R_i = A_{i,1}+A_{i,2}+\dots+A_{i,n}$（对所有 $1 \le i \le n$）；
• $C_j = A_{1,j}+A_{2,j}+\dots+A_{n,j}$（对所有 $1 \le j \le n$）；
• 换言之，$R_i$ 是网格 $A$ 各行的行和，$C_j$ 是各列的列和；
• 对于网格 $A$，定义其评价值为

  $$f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2,$$

  其中对于任意整数序列 $X$，$\max(X)$ 表示 $X$ 中的最大值，$\min(X)$ 表示 $X$ 中的最小值。

请找出任意一个满足上述条件的网格 $A$；在所有满足条件的网格中，找出任意一个使得 $f(A)$ 取得最小可能值的网格；在所有使 $f(A)$ 最小的网格中，任选其一即可。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case the only line contains two integers $n$, $k$ $(1 \le n \le 300, 0 \le k \le n^2)$.

It is guaranteed that the sum of $n^2$ for all test cases does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来的 $t$ 行每行描述一个测试用例。

每个测试用例仅有一行，包含两个整数 $n$ 和 $k$（$1 \le n \le 300$，$0 \le k \le n^2$）。

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

For each test case, firstly print the minimum possible value of $f(A)$ among all tables, for which the condition is satisfied.

After that, print $n$ lines contain $n$ characters each. The $j$-th character in the $i$-th line should be equal to $A_{i,j}$.

If there are multiple answers you can print any.

对于每个测试用例，首先输出所有满足条件的表格中 $f(A)$ 的最小可能值。

然后输出 $n$ 行，每行包含 $n$ 个字符。第 $i$ 行中的第 $j$ 个字符应等于 $A_{i,j}$。

若存在多个合法答案，输出任意一个即可。

In the first test case, the sum of all elements in the grid is equal to $2$, so the condition is satisfied. $R_1 = 1, R_2 = 1$ and $C_1 = 1, C_2 = 1$. Then, $f(A) = (1-1)^2 + (1-1)^2 = 0$, which is the minimum possible value of $f(A)$.

In the second test case, the sum of all elements in the grid is equal to $8$, so the condition is satisfied. $R_1 = 3, R_2 = 3, R_3 = 2$ and $C_1 = 3, C_2 = 2, C_3 = 3$. Then, $f(A) = (3-2)^2 + (3-2)^2 = 2$. It can be proven, that it is the minimum possible value of $f(A)$.

在第一个测试用例中，网格中所有元素的和等于 $2$，因此满足条件。$R_1 = 1, R_2 = 1$，且 $C_1 = 1, C_2 = 1$。于是，$f(A) = (1-1)^2 + (1-1)^2 = 0$，这是 $f(A)$ 可能取到的最小值。

在第二个测试用例中，网格中所有元素的和等于 $8$，因此满足条件。$R_1 = 3, R_2 = 3, R_3 = 2$，且 $C_1 = 3, C_2 = 2, C_3 = 3$。于是，$f(A) = (3-2)^2 + (3-2)^2 = 2$。可以证明，这是 $f(A)$ 可能取到的最小值。