Задача #4353

Количество программ

Уровень ЕГЭ

(А. Шуруха) Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Прибавь вес
Первая команда увеличивает число на экране на 1. Вторая команда увеличивает число на экране на количество единиц в его
двоичной записи.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 5 результатом является число 40?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы AAB при исходном числе 5 траектория состоит из чисел 6, 7, 10.

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

1463846

def f(c, e):
  if c > e: return 0
  if c == e: return 1
  r = 0
  r += f(c + 1, e) # A
  r += f(c + bin(c).count('1'), e) # B
  return r
print(f(5, 40))

Номер