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