Задание 16 ЕГЭ по информатике

34602572

Заметим, что $F(n)$ вычисляет сумму цифр десятичной записи числа, поэтому сделаем рекурсивную функцию, которая будет считать

количество числовых последовательностей, не превышающих $2^{63}-1$, сумма элементов которых равна $159$.

Пусть эта функция $f(\text{s}, \text{l}, \text{fl})$, где $\text{s}$ — сумма элементов, $\text{l}$ — длина оставшейся части последовательности, $\text{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))