Grid-00100 (Codeforces 1371D)
Tags: Greedy, constructive algorithms

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.

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

Output: 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.

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

Sample Inputs:
4
2 2
3 8
1 0
4 16

Sample Outputs:
0
10
01
2
111
111
101
0
0
0
1111
1111
1111
1111

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    (a, b) = (k // n, k % n)
    print(0 if b == 0 else 2)
    for i in range(n):
        if i < b and b != 0:
            if a + 1 + i <= n:
                print('0' * i + '1' * (a + 1) + '0' * (n - i - a - 1))
            else:
                print('1' * (a + 1 + i - n) + '0' * (n - a - 1) + '1' * (n - i))
        elif a + i <= n:
            print('0' * i + '1' * a + '0' * (n - a - i))
        else:
            print('1' * (a + i - n) + '0' * (n - a) + '1' * (n - i))

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 6)
import threading
input = stdin.readline

def ii():
    return int(input())

def lii():
    return list(map(int, stdin.readline().split()))

def ss():
    x = stdin.readline()
    if x and x[-1] == '\n':
        return x[:-1]
    return x

def lss():
    return list(map(str, stdin.readline().split()))

def llss():
    return [i for i in ss()]

def mpi():
    return map(int, input().split())

def yes(flag):
    if flag:
        stdout.write('YES\n')
    else:
        stdout.write('NO\n')

def pl(lst):
    stdout.write(' '.join(map(str, lst)) + '\n')

def ps(n):
    stdout.write(str(n) + '\n')
import heapq, math
from collections import defaultdict, deque

def main():
    for _ in range(ii()):
        (n, k) = mpi()
        ans = [['0'] * n for _ in range(n)]
        j = 0
        tp = n
        (mxr, mnr) = (0, n)
        for i in range(n):
            curr = math.ceil(k / tp)
            mxr = max(mxr, curr)
            mnr = min(mxr, curr)
            m = j
            temp = curr
            while temp:
                ans[i][m] = '1'
                m += 1
                m = m % n
                temp -= 1
            k -= curr
            tp -= 1
            j += 1
        res = (mxr - mnr) ** 2
        (mxc, mnc) = (0, n + 1)
        for i in range(n):
            tp = 0
            for j in range(n):
                tp += int(ans[j][i])
            mxc = max(mxc, tp)
            mnc = min(mnc, tp)
        res += (mxc - mnc) ** 2
        print(res)
        for i in ans:
            print(''.join(i))
threading.stack_size(2 * 10 ** 6)
t = threading.Thread(target=main)
t.start()
t.join()
''

Solution (Python):
from heapq import *
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    ans = [['0' for _ in range(n)] for _ in range(n)]
    if k % n == 0:
        print(0)
    else:
        print(2)
    i = 0
    j = 0
    for x in range(k):
        ans[i][j] = '1'
        i += 1
        j += 1
        j %= n
        if i == n:
            i = 0
            j += 1
            j %= n
    for i in ans:
        print(''.join(i))