ЕГЭ · ЗАДАНИЕ 13
Исполнители и количество программ · №31417
Даны команды: A: x → x + 1. B: дописать справа сумму цифр x. Команда разрешена, только если сумма меньше 10.
Сколько последовательностей команд переводят 3 в 200? Разные последовательности считаются разными программами.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать ответ
Ответ и пояснение
Ответ: 17
dp[x] — количество программ, приводящих к x. Начинаем с dp[start] = 1. Числа только увеличиваются, поэтому обходим их по возрастанию. Для каждой допустимой команды переносим dp[x] в состояние результата. Даже если две команды дают одно число, это две разные программы.
start, finish = 3, 200
dp = [0] * (finish + 1)
dp[start] = 1
for x in range(start, finish):
b = int(str(x)+str(sum(map(int,str(x))))) if sum(map(int,str(x))) < 10 else None
for y in (x + 1, b):
if y is not None and y <= finish:
dp[y] += dp[x]
print(dp[finish])