Обратная задача о черепашке
시간 제한3초메모리 제한256 MB
목표 경로 수 k가 주어질 때, 거북이의 단조 이동 경로 수가 정확히 k가 되도록 300x300 이하 격자의 허용 칸과 차단 칸을 구성한다.
문제
Одной из задач, решаемых методом динамического программирования, является задача о черепашке. Приведем условие этой задачи.
Задано поле размером n на m клеток. При этом для каждой клетки поля задано, является она разрешенной или запрещенной (левая верхняя и правая нижняя клетки обязательно разрешены). В левой верхней клетке находится черепашка. Черепашка за один ход может переместиться в соседнюю разрешенную клетку поля, которая находится либо справа, либо снизу от клетки, в которой она сейчас находится. Необходимо определить число путей, которыми черепашка может достичь правой нижней клетки поля, начав путь из левой верхней клетки.
Вам предлагается решить обратную задачу, а именно, найти такое поле, что число путей черепашки будет равно k.
입력
Первая строка содержит число k (1 ≤ k ≤ 1018).
출력
В первой строке выведите два целых числа, разделенных пробелом, — n и m. Эти числа не должны быть менее единицы или превышать 300.
Затем выведите n строк по m символов в каждой — описание поля. Разрешенной клетке поля должен соответствовать символ «1», запрещенной — «0». Левая верхняя и правая нижняя клетки поля должны быть разрешенными.
При наличии нескольких полей, удовлетворяющих указанным требованиям, выведите любое из них. Существование хотя бы одного такого поля гарантируется.