Красивая матрица
(Время: 1 сек. Память: 16 Мб Сложность: 56%)
Квадратная матрица – двумерный массив (таблица), составленный из N строк и N столбцов. Строки и столбцы матрицы нумеруются от 1 до N. Число N называют порядком матрицы.
Симметричная матрица – квадратная матрица A порядка N, которая симметрична своему горизонтальному и вертикальному отражению. Более формально: для любой пары (i,j) (1 ≤ i,j ≤ N) верно, что Ai,j = AN-i+1,j и Ai,j = Ai,N-j+1.
Красивая матрица – симметричная матрица, составленная из нулей и единиц таким образом, что никакие две клетки, содержащие единицы, не имеют общей стороны.
По заданному значению K требуется составить красивую матрицу, содержащую ровно K единиц. При этом порядок матрицы N должен быть минимально возможным.
Входные данные
Входной файл INPUT.TXT содержит единственное число K (1 ≤ K ≤ 1019) – количество единиц в матрице.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите число N – порядок матрицы. Если K ≤ 106, то в последующих N строках выведите N цифр в каждой строке без пробелов – искомую матрицу. Если существует несколько решений, выведите любое.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 4 | 3 010 101 010 |
2 | 9 | 5 01010 10001 00100 10001 01010 |
3 | 1234567 | 1573 |
Система оценки
Решения, работающие только для K ≤ 20, будут оцениваться в 20 баллов.
Решения, работающие только для K ≤ 106, будут оцениваться в 70 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|