Question

У исполнителя Калькулятор три команды, которым присвоены номера: 1 прибавь 1 2 прибавь 2 3 умножь на 3 Сколько есть программ, которые число 1 преобразуют в число 12?

Answer 1

1 1
2 1
3 1+1+1 = 3
4 1+3=4
5 3+4=7
6 1+4+7=12
7 19
8 31
9 53
10 84
11 137
12 137+84+4
Ответ:225

Answer 2

У исполнителя Калькулятор есть три команды: "прибавь 1", "прибавь 2" и "умножь на 3". Мы хотим узнать, сколько существует программ, которые преобразуют число 1 в число 12.

Мы можем решить эту задачу с помощью динамического программирования. Создадим массив dp, где dp[i] будет хранить количество программ, которые преобразуют число 1 в число i.

Изначально у нас есть только одна программа, которая состоит из пустой последовательности команд. Это программа, которая преобразует число 1 в число 1, поэтому dp[1] = 1.

Затем мы можем рассмотреть все числа от 2 до 12 и вычислить количество программ для каждого числа. Для каждого числа i мы можем получить его предыдущее число, вычтя 1, 2 или разделив на 3 (если i делится на 3 без остатка). Тогда количество программ для числа i будет равно сумме количеств программ для предыдущих чисел.

Итак, мы можем заполнить массив dp следующим образом:

dp[1] = 1 dp[2] = dp[1] (прибавляем 1) + 0 (нельзя преобразовать 1 в 2 с помощью "прибавь 2") + 0 (нельзя преобразовать 1 в 2 с помощью "умножь на 3") = 1 dp[3] = dp[2] (прибавляем 1) + 0 (нельзя преобразовать 1 в 3 с помощью "прибавь 2") + 0 (нельзя преобразовать 1 в 3 с помощью "умножь на 3") = 1 dp[4] = dp[3] (прибавляем 1) + dp[2] (прибавляем 2) + 0 (нельзя преобразовать 1 в 4 с помощью "умножь на 3") = 2 ... dp[12] = dp[11] (прибавляем 1) + dp[10] (прибавляем 2) + dp[4] (умножаем на 3) = 4 + 2 + 2 = 8

Таким образом, существует 8 программ, которые преобразуют число 1 в число 12, используя данные команды.