Grid-00100

题意翻译

给定 $n,k$。你需要构造出一个 $n \times n$ 的 $01$ 矩阵 $A$，**恰有 $k$ 个元素是 $1$**。 定义： - $A_{i,j}$ 为矩阵第 $i$ 行第 $j$ 列的元素 - $R_i=\sum\limits_{j=1}^{n} A_{i,j}$（$1 \leq i \leq n$） - $C_j=\sum \limits_{i=1}^{n} A_{i,j}$ （$1 \leq j \leq n$） - 换句话说，$R_i$ 是矩阵第 $i$ 行的和，$C_j$ 是矩阵第 $j$ 列的和 - 对于矩阵 $A$，定义 $f(A)=(\max(R)-\min(R))^2+(\max(C)-\min(C))^2$（此处对于一个正整数序列 $X$， $\max(X)$ 代表着 $X$ 中的最大值，$\min(X)$ 代表着 $X$ 中的最小值） 找到一个 $A$，使得 $f(A)$ 最小。你可以输出任意可行解。 多组数据，数据组数 $t \leq 100$，$1 \leq n \leq 300,0 \leq k \leq n^2,\sum n^2 \leq 10^5$ 翻译 by Meatherm

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

4
2 2
3 8
1 0
4 16

输出样例 #1

0
10
01
2
111
111
101
0
0
0
1111
1111
1111
1111

说明

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) $ .