Статья Автор: Лебедев Дмитрий

Разбор заданий HARD типа КЕГЭ-16

def f(n) :
  if n in dp : return dp[n]
  if n < 0 : 
    dp[n] = - f(-n)
    return dp[n]
  dp[n] = 2 * f(1-n) + 3*f(n-1) + 2
  return dp[n]
dp = {0 : 1}
n, A = 0, 50
while n < A :
  n += 1
  f(n)
  f(-n)
print(dp[A])

Главное не забыть, что в ответе требуется сумма цифр значения F(50), а не само значение

def f(n) :
  if n < -100000 : return 1
  if n in dp : return dp[n]
  if n > 10 : 
    dp[n] = f(n - 1) +3*f(n - 3) + 2
    return dp[n]
  dp[n] = - f(n-1)
  return dp[n]
dp = {}
n,  A = -100001, 20
while n < A :
  n += 1
  f(n)
print(dp[A])

Запустили рекурсию как динамику и ответ готов

def f(n) :
  if n >= 3210 : return 1
  if n in dp : return dp[n]
  dp[n] = f(n + 3) + 7
  return dp[n]
def g(n) :
  if n  < 10 : return n
  if n in gp : return gp[n]
  gp[n] = g(n - 3) + 5
  return gp[n]
dp, gp = {}, {}
for n in range(3001) :
  g(n)
for n in range(3210, 1,-1) :
  f(n)
print(dp[15] -gp[3000])

Надо понять, что вычисление для f и g надо проводить независимо и в разных направлениях

def f(n) :
  if n < 10 : return n
  if n in dp : return dp[n]
  if n < 1000 : 
    dp[n] = f(n // 10) +f(n % 10) 
    return dp[n]
  dp[n] = f(n // 1000) - f(n % 1000) 
  return dp[n]
dp = {}
n = -1
ans = 0
while n < 10**6 :
  n += 1
  r = f(n)
  if r == 0 : ans += 1
print(ans)

Просто запустили

def f(n) :
  if n < 3 : return 1
  if n in dp : return dp[n]
  if n % 2 == 0 :
    dp[n] = f(n -1) + g(n)
  else :
    dp[n] = f(n-2)- 2 * g(n + 1)
  return dp[n]
def g(n) :
  if n  < 3 : return 1
  if n % 2 == 0 : 
    gp[n] = f(n - 3) + f(n - 2)
  else :
    gp[n] = f(n+1) - g(n - 1)
  return gp[n]
dp, gp = {}, {}
for n in range(121) :
  g(n)
  f(n)
print(gp[120])

Странно, но работает !?

Прикрепленные файлы
report10748_1-4.05.2025a.xlsx

Печать