Динамическое программирование на таблицах

Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: \(C^k_n=C^{k-1}_{n-1}+C^{k}_{n-1}\), \(C^0_n = C^n_n=1\).
Входные данные
Вводится 2 числа - n и k.

Выходные данные
Необходимо вывести  значение  \(С^k_n\) .
 

Примеры

№	Входные данные	Выходные данные
1	4 2	6

В прямоугольной таблице NxM в левой верхней клетке стоит шашка. За один ход разрешается переместить шашку в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть вариантов переместить шашку в правую нижнюю клетку.


Входные данные
Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).

Выходные данные
Выведите искомое количество вариантов.
 

Примеры

№	Входные данные	Выходные данные
1	2 3	3

 

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Входные данные
Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

Выходные данные
Выведите единственное число –  количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.
 

Примеры

№	Входные данные	Выходные данные
1	1 2	4
2	2 3	50

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

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

Выходные данные
Выведите ответ на задачу

Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
 

Примеры

№	Входные данные	Выходные данные
1	3 4 abcd efdg hijk 4	abfdgk

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

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

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

Примеры

№	Входные данные	Выходные данные
1	1 1 1 0 100 0 1	1
2	2 2 0 0 10	6

Вася и Петя играют в следующую игру. Они берут колоду из 36 карточек. На каждой карточке написано число от 1 до 9 и каждая карточка покрашена в один из 4 цветов так, что есть ровно по 9 карточек каждого цвета и они пронумерованы числами от 1 до 9. Карты перемешиваются, и игрокам раздается по 18 карт.

Дальше игроки по очереди делают ходы. За один ход игрок может выложить на стол одну карточку по следующим правилам. Карточку с цифрой 5 можно выкладывать на стол в любой момент. Карточку с другой цифрой можно выкладывать только если на стол уже выложена карточка того же цвета, на которой написано число на 1 большее или на 1 меньшее, чем на данной карточке (не важно, была ли эта карточка выложена вами или вашим противником, и была ли она выложена на предыдущем ходе или раньше). Если игрок может выложить хоть какую-то карточку, он обязан делать ход. Если ни одну карточку игрок выложить не может, он пропускает ход.

Выигрывает тот, кто первым выложит все свои карточки на стол.

Напишите программу, которая по информации о том, кому какие карточки достались, определяет, кто выиграет при оптимальной игре обоих игроков.

Входные данные
Во входном файле записаны 18 пар чисел, описывающих карточки, которые достались первому игроку. Каждая карточка описывается двумя числами — номером цвета (от 1 до 4) и цифрой, которая написана на карточке (от 1 до 9). Второму игроку, соответственно, достались все остальные карточки.

Выходные данные
В выходной файл выведите одно число (1 или 2) — номер игрока, который выиграет при оптимальной игре обоих игроков.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9	1

Домовой Кузьма очень любит играть в шашки на доске 8х8. Когда никто не хочет с ним играть, он просто сидит и думает. Например, сейчас он пытается посчитать сколько есть вариантов провести белую шашку в дамки, если она находится одна на доске?
(Белая шашка ходит по диагонали на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

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

Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

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

Выведите одно число - количество вариантов.

 

 

Примеры

№	Входные данные	Выходные данные
1	3 7	2
2	1 8	1
3	3 6	4

 

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a₁, a₂, …, a_N. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

3
	1
		4
			1
				5
					9
						2
							6

Ввод	Вывод
8 3 1 4 1 5 9 2 6	5