Задача E. Матрёшки ≡

Условие

На столе стоят N матрёшек разного размера. Матрёшку меньшего размера можно поместить внутрь большей, ту, в свою очередь, внутрь ещё большей и так далее.

Сколькими способами можно поместить часть матрёшек внутрь других, чтобы осталось ровно K матрёшек?

Формат входного файла

Входной файл содержит целые числа N K.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — искомое число способов.

Ограничения

1 ≤ K ≤ N ≤ 12.

Примеры тестов

3 1

1

3 2

3

4 2

7

3 3

1

Разбор

(автор разбора А. Кленин)

Обозначим искомое число способов за f(N, K). Очевидно, что f(N, 1) = f(N, N) = 1, а f(x, K) = 0 для всех x < K.

В общем случае, в произвольном наборе из N матрёшек выберем самую большую. Пусть внутри этой матрёшки поместятся i других (i = 0… N − 1). Этих матрёшек можно выбрать C(i, N − 1) способами, где C — число сочетаний. Из остальных матрёшек нужно оставить K − 1, что можно сделать f(N − i − 1, K − 1) способами.

Таким образом, рекуррентное соотношение имеет вид f(N, K) = ΣN − 1i = 0C(i, N − 1) * f(N − i − 1, K − 1).

Вычисления легко реализовать с помощью рекурсивной функции. Для оптимизации можно применить метод динамического программирования, однако ограничения в данной задаче таковы, что это не требуется для полного решения.