Задача #1601

Рекурсия

Сложнее ЕГЭ

(С. Чайкин) Алгоритм вычисления значения функции $F (n)$ , где $n$ — целое число, задан следующими соотношениями:

$F (n) = {\begin{matrix} n, & если n < 10, \\ F (n % 10) + F (n / / 10), & если n ⩾ 10 \end{matrix}$

Определите количество натуральных значений $n$ , меньших $2^{63}$ , для которых $F (n) = 159$ .

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

34602572

Заметим, что $F (n)$ вычисляет сумму цифр десятичной записи числа, поэтому сделаем рекурсивную функцию, которая будет считать
количество числовых последовательностей, не превышающих $2^{63} - 1$ , сумма элементов которых равна $159$ .
Пусть эта функция $f (s, l, fl)$ , где $s$ — сумма элементов, $l$ — длина оставшейся части последовательности, $fl$ — "особый флаг".
Главная сложность задачи — ограничить выбор элементов в рекурсии, чтобы находить только числа, которые меньше верхней границы.
Одним из возможных способов решения является ограничение следующей цифры. Для примера изменим наше ограничение с $2^{63}$ на $2^{4}$ . Очевидно, что на первом месте последовательности может быть только 2 цифры (0 и 1). Если выбрать 0, то следующая цифра может быть любой, так как наше число никак не сможет превысить верхнюю границу. Если же выбрать 1, следующая цифра не может быть больше 5, так как в ином случае у нас могут быть числа не менее 16. Таким образом, зная текущую цифру, мы можем заранее сказать, какое ограничение будет у следующей цифры. Если хотя бы одна цифра в записи меньше граничной, все последующие цифры могут принимать значение от 0 до 9. Чтобы правильно работать с этим ограничением и нужен параметр fl.

from functools import *

# граничное значение
a = list(map(int, str(2**63-1)))

@cache
def f(s, l, fl):
    # если последовательность нужной длины, проверяем, что сумма нам подходит,
    # и выходим из рекурсии.
    if l == 0: return s == 159

    # проверяем ограниченные подпоследовательности большей длины
    return sum(f(s+x, l-1, fl and (x == a[-l])) for x in range([10, a[-l]+1][fl]))

# ответ - количество ограниченных последовательностей необходимой длины
print(f(0, len(a), 1))

Номер