5. Касты

Используем динамическое программирование и длинную арифметику для расчета количества чисел с заданной суммой. В ячейке `T[K,S]` таблицы для динамического программирования хранится количество номеров из `K` цифр с суммой `S`. Построив таблицу `T` до `K`-ой строки можно построить `(K+1)` строку, выполнив суммирование для `S` от 0 до `K*9` и для `j` от 0 до 9 `T[K+1,S+j]:=\ T[K+1,S+j]+T[K,S]`. Для вычислений нужны только 2 строки таблицы.

Лобовой вариант – перебор всех чисел от 0 до `10^N` и подсчет количества чисел с заданной суммой среди них давал 8 баллов. 18 баллов можно было получить с помощью динамического программирования и таблицы `T` с ячейками типа extended для `N\ <\ 20`.