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