Задача #1790
Количество программ
У исполнителя Кузнечик две команды:
- Прибавь 3
- Вычти 2
Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).
Программа для Кузнечика – это последовательность команд.
Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 68 команд?
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
69
Видео по задаче
from functools import *
@lru_cache(None)
def f(x, c):
if c == 68:
ans.add(x)
return
f(x+3, c+1)
f(x-2, c+1)
ans = set()
f(1, 0)
print(len(ans))