Помогите решить 16 задание ЕГЭ по Информатике

Question

Помогите решить 16 задание ЕГЭ по Информатике

Никита Антропов Ученик (153), открыт 6 дней назад

Столкнулся с проблемой переполнения памяти в решении задачи.

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F ( n ) = 1 , если n ⩽ 1 ; F (n)=f (n−1)×f (n−2)+f (1), если n >1 и n кратно 100; F (n)=n ×f (n−1), если n >1 и n не кратно 100; Определите, сколько раз будет выполнена функция F при вычислении F(2042). Никакие предыдущие значения не кешируются и учитываются суммарно. Например при вычислении F ( 3 ) + F ( 1 ) F(3)+F(1) будут выполнены вызовы F ( 3 ) F(3) и F ( 2 ) F(2) по одному разу и F ( 1 ) F(1) дважды, поэтому ответ для F ( 3 ) + F ( 1 ) F(3)+F(1) будет равен 4. В ответе укажите только число — количество вызовов.

Answer 1

 f = [1, 1] + [0] * 2041 
for n in range(2, 2043): 
  f[n] = [f[n - 1], f[n - 1] + f[n - 2] + f[1]][n % 100 == 0] + 1 
print(f[2042])