Подберите такую таблицу , где , каждая клетка которой либо свободна, либо занята, чтобы количество путей из клетки в клетку длины по свободным клеткам было равно заданному числу . Нумерация клеток идет сверху вниз, слева направо. Формат ввода В

Добавлена: 02.05.2026
Обновлена: 02.05.2026
Предмет: Другое
Автор: Кэмп

Условие:

\begin{array}{|l|l|} \hline Ограничение времени & 1 секунда \\ \hline Ограничение памяти & 64 Мб \\ \hline Ввод & стандартный ввод или input.txt \\ \hline Вывод & стандартный вывод или output.txt \\ \hline \end{array}

Подберите такую таблицу $n \times m$ , где $1 \leq n, m \leq 120$ , каждая клетка которой либо свободна, либо занята, чтобы количество путей из клетки $(1,1)$ в клетку $(n, m)$ длины $n+m-1$ по свободным клеткам было равно заданному числу $k$ . Нумерация клеток идет сверху вниз, слева направо.

Формат ввода В единственной строке входа записано число $k, 1 \leq k \leq 10^{17}$ .

Формат вывода В первой строке два числа $n$ и $m$ - размеры таблицы, $1 \leq n, m \leq 120$ . В следующих $n$ строках по $m$ символов, описывающих таблицу. Свободная клетка кодируется символом ., занятая - символом #.

Гарантируется, что для данного $k$ существует ответ.

Решение:

Ниже описывается один из способов построения лабиринта, удовлетворяющего условию задачи «Лабиринт Паскаля». Заметим, что требуемые пути должны иметь ровно длину n+m–1 (то есть идти строго вправо и вниз), а число таких путей в полностью свободном прямоугольнике n×m равно биномиальному коэффициенту C(n+m–2, n–1). Но k может быть любым числом от 1 до 10^17, а не обязательно биномиальным коэффициентом; значит, нам нужно расставить препятствия так, чтобы изначальный «паскальевский» ход динамики (dp[i][j] = dp[i–1][j] + dp[i][j–1]) дал ровно k путей.

Пример идеи решения:

...