Рассмотрим функцию от трех переменных 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 тоже подходит).
Граничные условия попробуйте написать самостоятельно. Сделав это, Вы поймете, что написать итеративное решение за время проведения олимпиады практически невозможно (чемпионы не в счет).
Справедливости ради заметим, что задача допускает строгое математическое решение, связанное с подсчетом сочетаний, но оно ненамного эффективнее рассмотренного здесь.