Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 28 и при этом траектория вычислений содержит число 25 и не содержит число 10?

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно использовать метод динамического программирования.

Пусть dp[n] - количество программ, результатом которых является число n и которые содержат число 25 и не содержат число 10.

Инициализируем dp[1] = 1 (так как изначальное число 1 и не содержит число 10).

Затем перебираем все числа n от 2 до 28 и вычисляем значения dp[n] по следующей формуле:

dp[n] = dp[n-1] + dp[n/2], если число n не делится на 2.

dp[n] = dp[n-1], если число n делится на 2.

Таким образом, перебрав все числа от 2 до 28, мы найдем количество программ, удовлетворяющих условиям задачи.