Страница: 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
#111880
Скайлайн
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Вы хотите, чтобы небоскребы в вашем городе имели красивый вид. Решено построить N небоскребов в ряд. У небоскреба с номером \(i\) должно быть ровно \(h[i]\) этажей.

У Вас есть предложения от различных строительных компаний. Первая из них предлагает строить один этаж в любом из небоскребов за 3 миллиона евро. Вторая предлагает строить по одному этажу в каждом из двух соседних небоскребов за 5 миллионов евро. Заметим, что не имеет значения, находятся ли эти этажи на одинаковой высоте или нет. Третья компания предлагает строить по одному этажу в каждом из трех последовательных небоскребах за 7 миллионов евро.

Вы можете построить этажи в любом порядке. Вычислите минимальную необходимую сумму денег для строительства.

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

Первая строка содержит одно целое число \(N\) (1 \(\le\) \(N\) \(\le\) 300). Вторая строка содержит \(N\) целых чисел h[1], h[2] ..., h[N], 1 \(\le\) h[i] \(\le\) 200.

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

В единственной строке выведите одно целое число: минимальную сумму денег для строительства, в миллионах.

Примеры
Входные данные
3
2 2 2
Выходные данные
14
Входные данные
4
1 3 1 1
Выходные данные
15
#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 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест