Страница: 1 Отображать по:
#111877
Энергичная черепаха
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Дана сетка с \(N\) + 1 рядами и \(M\) + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (\(N\), \(M\)). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем \(T\) раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (\(N\), \(M\)). Так как это число может быть очень большим, выведите остаток от его деления на \(Z\).

Входные данные

В первой строке входного файла задается 5 целых чисел: \(N\), \(M\), \(K\), \(T\) и \(Z\) (\(1\) \(\le\) \(N\),\(M\) \(\le\) 300000, 0 \(\le\) \(K\), \(T\) \(\le\) 20, 1 \(\le\) \(Z\) \(\le\) \(10^9\)). В каждой из следующих \(K\) строк расположены координаты соответствующей клетки с ловушкой \(X\), \(Y\) (0 \(\le\) \(X\) \(\le\) \(N\), 0 \(\le\) \(Y\) \(\le\) \(M\)). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (\(N\), \(M\)) ловушек нет.

Выходные данные

Выведите требуемое число.

Примеры
Входные данные
1 1 1 0 100
0 1
Выходные данные
1
Входные данные
2 2 0 0 10
Выходные данные
6
#111882
K-й путь
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

У вас есть таблица c \(N\) строками и \(M\) столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка  значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение \(K\)-го пути в этом отсортированном листе.

Входные данные

В первой строке задается два целых числа \(N\)  количество рядов и \(M\)  количество столбцов заданной таблицы (1 \(\le\) \(N\), \(M\) \(\le\) 30). Каждая из следующих \(N\) строк содержит ровно \(M\) строчных букв английского алфавита. Последняя строка входного файла содержит целое число \(K\) (1 \(\le\) \(K\) \(\le\) 1018). Гарантируется, что для \(K\) ответ всегда существует.

Выходные данные

Первая и последняя строка выходного файла должна содержат одну строку - ответ к задаче.

Пояснения к примеру

abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk

Примеры
Входные данные
3 4
abcd
efdg
hijk
4
Выходные данные
abfdgk
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест