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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ K ≤ N ≤ 12.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
1
2
3 2
3
3
4 2
7
4
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).

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

Скачать файл с разбором Г. Гренкина

0.155s 0.010s 15