Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: А. Вычесть 1 В. Вычесть 4 С. Найти целую часть от деления на 2 Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 30 результатом является число 4, при этом траектория вычислений не содержит числа 8 и содержит 12? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы САВ при исходном числе 13 траектория состоит из чисел 6, 5, 1.

Решение:

Обозначим количество программ, приводящих из числа x к числу y, через N(x, y). Нам нужно найти количество программ, которые при исходном числе 30 приводят к числу 4, не содержат в траектории число 8 и содержат число 12.

Шаг 1: Найдём общее количество программ из 30 в 4.

Для этого будем двигаться обратно от числа 4 к числу 30, используя обратные команды:

• Обратная команде 'А. Вычесть 1' — 'Прибавить 1'.
• Обратная команде 'В. Вычесть 4' — 'Прибавить 4'.
• Обратная команде 'С. Найти целую часть от деления на 2' — 'Умножить на 2' или 'Умножить на 2 и прибавить 1'.

Обозначим f(n) как количество программ, переводящих число n в число 4.

• f(4) = 1 (пустая программа)
• f(5) = f(4) = 1 (только команда А)
• f(6) = f(5) + f(2). Нужно вычислить f(2).
• f(2) = f(1) = f(0).
• f(1) = f(0).
• f(0) = 1 (пустая программа, если мы можем остановиться на 0)

Этап обратного отсчёта сложен, поэтому перейдём к прямому подсчёту.

Шаг 2: Построим дерево вычислений или используем динамическое программирование.

Обозначим dp[i] как количество программ, которые преобразуют число i в число 4, с учётом ограничений.

Нас интересует dp[30], при условии, что 8 не встречается, а 12 встречается.

Сначала рассмотрим задачу без ограничения на 12, но с запретом на 8.

dp[4] = 1

dp[5] = dp[4] = 1 (команда А)

dp[6] = dp[5] + dp[2]. Для простоты, будем считать, что числа меньше 4 не достигают 4, поэтому dp[n] = 0 для n < 4.

dp[6] = dp[5] + dp[2] = 1 + 0 = 1 (через 5)

dp[7] = dp[6] + dp(3) = 1 + 0 = 1

dp[8] = 0 (запрещено)

dp[9] = dp[8] + dp[5] = 0 + 1 = 1

dp[10] = dp[9] + dp[6] = 1 + 1 = 2

dp[11] = dp[10] + dp(7) = 2 + 1 = 3

dp[12] = dp[11] + dp[8] = 3 + 0 = 3

dp[13] = dp[12] + dp(9) = 3 + 1 = 4

dp[14] = dp[13] + dp[10] = 4 + 2 = 6

dp[15] = dp[14] + dp(11) = 6 + 3 = 9

dp[16] = dp[15] + dp(12) = 9 + 3 = 12

dp[17] = dp[16] + dp(13) = 12 + 4 = 16

dp[18] = dp[17] + dp(14) = 16 + 6 = 22

dp[19] = dp[18] + dp(15) = 22 + 9 = 31

dp[20] = dp[19] + dp(16) = 31 + 12 = 43

dp[21] = dp[20] + dp(17) = 43 + 16 = 59

dp[22] = dp[21] + dp(18) = 59 + 22 = 81

dp[23] = dp[22] + dp(19) = 81 + 31 = 112

dp[24] = dp[23] + dp(20) = 112 + 43 = 155

dp[25] = dp[24] + dp(21) = 155 + 59 = 214

dp[26] = dp[25] + dp(22) = 214 + 81 = 295

dp[27] = dp[26] + dp(23) = 295 + 112 = 407

dp[28] = dp[27] + dp(24) = 407 + 155 = 562

dp[29] = dp[28] + dp(25) = 562 + 214 = 776

dp[30] = dp[29] + dp(26) = 776 + 295 = 1071

Теперь учтём условие, что траектория должна содержать число 12.

Нам нужно найти количество программ из 30 в 12 (без 8) и из 12 в 4 (без 8).

Шаг 3: Подсчёт программ из 30 в 12 (без 8).

Продолжим предыдущий подсчёт, но остановимся на 12.

dp[4..7] — как выше.

dp[8] = 0

dp[9] = 1

dp[10] = 2

dp[11] = 3

dp[12] = 3

Теперь найдём количество программ из 30 в 12, учитывая, что 8 не должно встречаться.

Обозначим N(x, y) — количество программ из x в y, без числа 8.

N(4, 4) = 1

N(5, 4) = 1

N(6, 4) = N(5, 4) + N(2, 4) = 1 + 0 = 1

N(7, 4) = N(6, 4) + N(3, 4) = 1 + 0 = 1

N(8, 4) = 0 (запрещено)

N(9, 4) = N(8, 4) + N(5, 4) = 0 + 1 = 1

N(10, 4) = N(9, 4) + N(6, 4) = 1 + 1 = 2

N(11, 4) = N(10, 4) + N(7, 4) = 2 + 1 = 3

N(12, 4) = N(11, 4) + N(8, 4) = 3 + 0 = 3

Теперь найдём N(30, 12). Это можно сделать, вычислив N(x, 12) для x от 12 до 30.

N(12, 12) = 1 (пустая программа)

N(13, 12) = N(12, 12) + N(9, 12) = 1 + 0 = 1

N(14, 12) = N(13, 12) + N(10, 12) = 1 + 0 = 1

N(15, 12) = N(14, 12) + N(11, 12) = 1 + 0 = 1

N(16, 12) = N(15, 12) + N(12, 12) = 1 + 1 = 2

N(17, 12) = N(16, 12) + N(13, 12) = 2 + 1 = 3

N(18, 12) = 0 (запрещено)

N(19, 12) = N(18, 12) + N(15, 12) = 0 + 1 = 1

N(20, 12) = N(19, 12) + N(16, 12) = 1 + 2 = 3

N(21, 12) = N(20, 12) + N(17, 12) = 3 + 3 = 6

N(22, 12) = N(21, 12) + N(18, 12) = 6 + 0 = 6

N(23, 12) = N(22, 12) + N(19, 12) = 6 + 1 = 7

N(24, 12) = N(23, 12) + N(20, 12) = 7 + 3 = 10

N(25, 12) = N(24, 12) + N(21, 12) = 10 + 6 = 16

N(26, 12) = N(25, 12) + N(22, 12) = 16 + 6 = 22

N(27, 12) = N(26, 12) + N(23, 12) = 22 + 7 = 29

N(28, 12) = N(27, 12) + N(24, 12) = 29 + 10 = 39

N(29, 12) = N(28, 12) + N(25, 12) = 39 + 16 = 55

N(30, 12) = N(29, 12) + N(26, 12) = 55 + 22 = 77

Количество программ из 30 в 12 (без 8) равно 77.

Шаг 4: Подсчёт программ из 12 в 4 (без 8).

Мы уже вычислили это в Шаге 2: dp[12], где dp[i] — количество программ из i в 4 без числа 8.

dp[12] = 3.

Шаг 5: Вычисление итогового ответа.

Общее количество программ, удовлетворяющих условиям, равно произведению количества программ из 30 в 12 (без 8) и количества программ из 12 в 4 (без 8).

Итого = N(30, 12) * dp[12] = 77 * 3 = 231

Ответ: 231