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

Разбор некоторых заданий из вариантов Горбачева

Здесь будут ссылки

Задание 23. Вариант 3

Похоже, что сложность вызвали слова только в условии. Если про него забыть то ответом будет число 1180, что неверно
Попробуем написать простую динамическую программу

def f(n) :
  if n in dp : return dp[n] # возврат уже полученного
  if (n-sf[0])*(n-sf[1])> 0 : return 0 # проверка выхода за пределы обработки
  dp[n] = f(n-1) # вычисление нового значения - базовая часть
  if n % 2 == 0 : dp[n] += f(n//2) # проверка на кратность 2 и добавление
  if n % 3 == 0 : dp[n] += f(n//3) # проверка на кратность 3 и добавление
  return dp[n]
start, end =122 , 57 # Первый прогон из 122 в 57
sf= [start,end]
dp = {end : 1}
a = f(start)
start, end = 57, 11 # Второй прогон из 57 в 11 (создан копирование с удалением 122 и добавлением 11)
sf= [start,end]
dp = {end : 1}
b = f(start) # a заменили на b
print(a*b, a, b)  # итоговый вывод

Задание 23, вариант 2

Для решения этого задания можно использовать разные подходы:

I: перебирать все возможные/допустимые траектории - и считать, сколько из них "добежит" до 155
II: добавить к состоянию команду, по которой пришли. В данном случае можно считать, что в 5 попали по команде A
( в общем случае/например, при запрете повтора команды/ можно "принудительно" выполнить 1 команду и суммировать запуски)

Более просто реализовать метод II - он похож на "игровую с двумя кучами"

def f(pos) :
  if pos in dp : return dp[pos] # возврат уже полученного
  n, k = pos # n - число, k - номер команды (A = 1, B= 2, C =3)
  if (n-sf[0])*(n-sf[1])> 0 : return 0 # проверка выхода за пределы обработки
  dp[pos] = f((n+1,1)) + f((n*n, 3))
  if k != 2 : 
    dp[pos] += f((2*n,2)) # вычисление нового значения - базовая часть
  return dp[pos]
start, end =5 , 80 # Первый прогон из 5 в 80
sf= [start,end]
dp = {(end,1) : 1, (end,2) : 1,(end,3) : 1, (40,1) : 0, (40,2) : 0, (40,3) : 0}
print(f((start,1)))

Запустив код, получим число 400.
Теперь вроде надо запустить вторую половину кода из 80 в 155!!!
Но надо ли? К числу 80 можно применить только команду A!? Значит путь из 80 в 155 единственный и => 400 - это ответ.
Вопрос, а что делать, если надо было бы

попасть в 1580? (запрет на 40 упрощает решение)
не было бы запрета на 40 и в 1580?

Задание 23, вариант 4

Чем интересно это задание? Тем, что финальных точек несколько, хотя они лежат плотно.
Решение стандартное динамическое, но строго "вначале возврат, а затем проверка выхода"

def f(n) :
  if n in dp : return dp[n] # возврат уже полученного
  if (n-sf[0])*(n-sf[1])> 0 : return 0 # проверка выхода за пределы обработки
  dp[n] = f(n + 3) + f(n + 4) + f(n * 2) # вычисление нового значения 
  return dp[n]
start, end = 11 , 55 # Прогон из 11 в [51;54]
sf= [start,end]
dp = {23 : 0} # занесли запрет
for i in range(end - 5,end): # занесли финалы
  dp[i] = 1
a = f(start)
print(a)  # итоговый вывод

Как может быть "усилить" задание?

сделать разрыв между финальными точками (в разрывы) можно заходить
испрользовать интервал значений как "кочку"
Например, из 11 в 1580 через отрезок [50;54] (обязательно, но строго через одну)

Задание 16, вариант 3

Понятно, что можно/нужно делать руками, но следаем простой динамической рекурсией

def f(n) :
  if n in dp : return dp[n] # возврат уже полученного
  dp[n] = 7*n*f(n-2) # вычисление нового значения - базовая часть
  return dp[n]
porog = 9242 # задание порога для вычислений
dp = {10 : 10} # задание и заполнение словаря
for i in range(1,10):
  dp[i] = 10
i = 0
while i < porog :
  i += 1
  f(i)
a = dp[porog] - dp[porog-1]
b = dp[porog-2]
print(a*19/b)  # итоговый вывод

Чтобы оставить комментарий нужна авторизация

Печать