Форум » Динамическое программирование » Не сходится ответ к задаче 7371 » Ответить
Не сходится ответ к задаче 7371
neuroherring: Программа вообще выдает превышение рекурсии при запуске, но даже на маленький числах получаются гораздо большие ответы, например сумма до 51 уже 45 получается, а в ответе всего 37. Да и не может быть в принципе такого маленького ответа мне кажется [pre2] F = {} def f(n): if n in F: return F[n] elif n == 0: return 1 elif n < 0: return 0 else: F.update({n:f(n-1) + f(n-3) + f(n-5)}) return F[n] print(sum(int(k) for k in (str(f(112500))))) [/pre2]
Ответов - 1
Ж: Ответ маленький, т.к. это не число способов, а сумма цифр этого числа. [pre2] k=0 for a in range(112500//5+1): k+=(112500-a*5)//3+1 print(sum(int(c) for c in str(k))) [/pre2] Рассуждения таковы: Ведем перебор по количеству пятерок (112500//5+1 - +1 , т.к. включительно надо), тогда троек столько, сколько чисел в оставшейся сумме делится на 3 (+1, т.к. троек может и не быть).
полная версия страницы