Безумный ученый Dr.Jubal придумал задачу по программированию. Попробуйте решить ее!
Вам даны целые числа \(n,k\). Постройте таблицу \(A\), имеющую размер \(n \times n\) и состоящую из целых чисел \(0\) или \(1\). Должно быть выполнено очень важное условие: сумма всех элементов в таблице равна \(k\). Другими словами, количество чисел \(1\) в таблице равно \(k\).
Давайте определим:
- \(A_{i,j}\) как число, стоящее в \(i\)-й строке и \(j\)-м столбце.
- \(R_i = A_{i,1}+A_{i,2}+...+A_{i,n}\) (для всех \(1 \le i \le n\)).
- \(C_j = A_{1,j}+A_{2,j}+...+A_{n,j}\) (для всех \(1 \le j \le n\)).
- Другими словами, \(R_i\) это суммы чисел в строках и \(C_j\) это суммы чисел в столбцах таблицы \(A\).
- Для таблицы \(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)\) среди всех таблиц, для которых условие выполнено.
После этого, выведите \(n\) строк, каждая содержит по \(n\) символов. \(j\)-й символ в \(i\)-й строке должен быть равен \(A_{i,j}\).
Если есть несколько возможных решений, вы можете вывести любое.
Примечание
В первом наборе входных данных сумма всех чисел таблицы равна \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 2
3 8
1 0
4 16
|
0
10
01
2
111
111
101
0
0
0
1111
1111
1111
1111
|