1371D.md (2565B)
1 Source: https://codeforces.com/problemset/problem/1371/D 2 3 D. Grid-00100 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A mad scientist Dr.Jubal has made a competitive programming task. Try to solve it! 22 23 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$. 24 25 Let's define: 26 27 * $A_{i,j}$ as the integer in the $i$-th row and the $j$-th column. 28 * $R_i = A_{i,1}+A_{i,2}+...+A_{i,n}$ (for all $1 \le i \le n$). 29 * $C_j = A_{1,j}+A_{2,j}+...+A_{n,j}$ (for all $1 \le j \le n$). 30 * In other words, $R_i$ are row sums and $C_j$ are column sums of the grid $A$. 31 * 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$). 32 33 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. 34 35 Input 36 37 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. 38 39 For each test case the only line contains two integers $n$, $k$ $(1 \le n \le 300, 0 \le k \le n^2)$. 40 41 It is guaranteed that the sum of $n^2$ for all test cases does not exceed $10^5$. 42 43 Output 44 45 For each test case, firstly print the minimum possible value of $f(A)$ among all tables, for which the condition is satisfied. 46 47 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}$. 48 49 If there are multiple answers you can print any. 50 51 Example 52 53 Input 54 55 ``` 56 4 57 2 2 58 3 8 59 1 0 60 4 16 61 ``` 62 63 Output 64 65 ``` 66 0 67 10 68 01 69 2 70 111 71 111 72 101 73 0 74 0 75 0 76 1111 77 1111 78 1111 79 1111 80 ``` 81 82 Note 83 84 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)$. 85 86 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)$.