시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 256 MB | 0 | 0 | 0 | 0.000% |
Одной из задач, решаемых методом динамического программирования, является задача о черепашке. Приведем условие этой задачи.
Задано поле размером n на m клеток. При этом для каждой клетки поля задано, является она разрешенной или запрещенной (левая верхняя и правая нижняя клетки обязательно разрешены). В левой верхней клетке находится черепашка. Черепашка за один ход может переместиться в соседнюю разрешенную клетку поля, которая находится либо справа, либо снизу от клетки, в которой она сейчас находится. Необходимо определить число путей, которыми черепашка может достичь правой нижней клетки поля, начав путь из левой верхней клетки.
Вам предлагается решить обратную задачу, а именно, найти такое поле, что число путей черепашки будет равно k.
Первая строка содержит число k (1 ≤ k ≤ 1018).
В первой строке выведите два целых числа, разделенных пробелом, — n и m. Эти числа не должны быть менее единицы или превышать 300.
Затем выведите n строк по m символов в каждой — описание поля. Разрешенной клетке поля должен соответствовать символ «1», запрещенной — «0». Левая верхняя и правая нижняя клетки поля должны быть разрешенными.
При наличии нескольких полей, удовлетворяющих указанным требованиям, выведите любое из них. Существование хотя бы одного такого поля гарантируется.
2
2 3 111 011
Contest > Russian Code Cup > 2011 > RCC 2011 Final Round B번