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