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