|
Название задачи: Паровозики. |
 |
Условие
N локомотивов, имеющих номера от 1 до N и установленных на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью.Написать программу, определяющую, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов.
Формат входных данных
Два числа — 0 < N < 17 и 0 < p < N + 1.
Формат выходных данных
Одно число — s.
Решение
Рассмотрим функцию от трех переменных F(X, Y, Z), которая показывает число расстановок при которых Y паровозиков образуют Z групп, причем самый первый паровозик имеет номер X. Для ответа достаточно просуммировать эту функцию по первой переменной. Разберем, чему наша функция равна. Возможны два варианта - первый паровозик образует отдельную группу или тормозит хотя бы один локомотив за собой. В первом случае необходимо суммировать выражения вида F(I, Y - 1, Z - 1) при I < X (действительно, если "наш паровоз вперед летит", то лидер хвоста должен иметь меньший номер и при этом образуется на одну группу меньше). Во втором случае - F(I, Y - 1, Z) при I > X (лидер имеет больший номер и при этом образуется столько же групп).
function F(x, y, z : byte) : Tcal; var i : byte; s : Tcal; begin if D[x, y, z] = -1 then begin s := 0; for i := 1 to x - 1 do s := s + F(i, y - 1, z - 1); for i := x + 1 to y do s := s + F(x, y - 1, z); D[x, y, z] := s end; F := D[x, y, z] end;
Обратите внимание на тип Tcal. Дело в том, что типа LongInt недостаточно, поэтому требуется использование иных средств. В данном случае положение спасает тип Comp (Double тоже подходит).
Граничные условия попробуйте написать самостоятельно. Сделав это, Вы поймете, что написать итеративное решение за разумное время довольно сложно.
Справедливости ради заметим, что задача допускает строгое математическое решение, связанное с подсчетом сочетаний, но оно ненамного эффективнее рассмотренного здесь.
