codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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