Отправлено: 31.01.24 20:19. Заголовок: Разберите решение для 7178

Я перепробовал множество решений(с помощью рекурсии). Но всё сводится к недостатку памяти, либо к бесконечному алгоритму.
result = []
po = 0
def f(x,y,way:list):
global po
if x == y:
result.append(way)
po += 1
return 1
elif x > y:
return 0
else:
return f(x+2,y,way.copy())+f(x+3,y,way.copy())+f(x*3,y,way.copy())
print("Total",f(1,123,[1]))

Это я уже просто отчаялся и решил записывать пути в массив, чтобы потом их разобрать. Но этот алгоритм приводит к недостатку памяти, что логично. А все остальные выполняются больше 8минут(дальше я не замерял). В ответах написано, что ответ 60, а значит, число подходящих решений должно быть больше 9**6.

 Отправлено: 17.02.24 22:18. Заголовок: Даже не возьмусь вня..

Даже не возьмусь внятно объяснить, что делает этот код. Но ответ он выдает верный. И считает мгновенно.
Но суть примерно такова:
Максимальное число операций меньше 65.
После каждого шага мы определяем количество способов получить очередное число, учитывая только разницу в количестве четных и нечетных чисел в траектории. Если одно и то же число с одинаковой разницей можно получить несколькими способами, складываем их и храним единожды в словаре.

 
 kol=0; c={(1,1):1} 
 for k in range(65): 
     d={} 
     for e in c: 
         if e[0]%2==0: zn=-1 
         else: zn=1 
         if e[0]+2<=123: 
             if (e[0]+2,e[1]+zn) not in d: d[e[0]+2,e[1]+zn]=c[e] 
             else: d[e[0]+2,e[1]+zn]+=c[e] 
         if e[0] + 3 <= 123: 
             if (e[0] + 3, e[1] - zn) not in d: d[e[0] + 3, e[1] - zn] = c[e] 
             else: d[e[0] + 3, e[1] - zn] += c[e] 
         if e[0] *3 <= 123: 
             if (e[0]*3,e[1]+zn) not in d: d[e[0]*3,e[1]+zn]=c[e] 
             else: d[e[0]*3,e[1]+zn]+=c[e] 
     c=d 
     kol+=sum([c[t] for t in c if t[0]==123 and t[1]==0]) 
     # print(d) 
 print(kol,sum(int(c) for c in str(kol)))