Преобразование чисел исполнителем

Задание

Исполнитель  преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1) Прибавить 1

2) Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. 

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 34 и при этом траектория вычислений содержит число 12?

(Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.)

Решение

2 -> 12: 10 траекторий

1)  [2,3,4,5,6,7,8,9,10,11,12]−[1,1,1,1,1,1,1,1,1,1] 

2)  [2,3,4,5,6,12]−[1,1,1,1,2] 

3)  [2,3,4,5,10,11,12]−[1,1,1,2,1,1] 

4)  [2,3,4,8,9,10,11,12]−[1,1,2,1,1,1,1] 

5)  [2,3,6,7,8,9,10,11,12]−[1,2,1,1,1,1,1,1] 

6)  [2,4,5,6,7,8,9,10,11,12]−[2,1,1,1,1,1,1,1,1] 

7)  [2,4,5,6,12]−[2,1,1,2] 

8)  [2,4,5,10,11,12]−[2,1,2,1,1] 

9)  [2,4,8,9,10,11,12]−[2,2,1,1,1,1] 

10)  [2,3,6,12]−[1,2,2] 

12 -> 34:  7 траекторий 

1)  [12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]−

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] 

2)  [12,13,14,15,16,17,34]−[1,1,1,1,1,2] 

3)  [12,13,14,15,16,32,33,34]−[1,1,1,1,2,1,1] 

4)  [12,13,14,15,30,31,32,33,34]−[1,1,1,2,1,1,1,1] 

5)  [12,13,14,28,29,30,31,32,33,34]−[1,1,2,1,1,1,1,1,1] 

6)  [12,13,26,27,28,29,30,31,32,33,34]−[1,2,1,1,1,1,1,1,1,1] 

7)  [12,24,25,26,27,28,29,30,31,32,33,34]−[2,1,1,1,1,1,1,1,1,1,1] 

Итого: 10 x 7  = 70 программ 

Например:

[2,3,6,12,24,25,26,27,28,29,30,31,32,33,34]−[1,2,2,2,1,1,1,1,1,1,1,1,1,1]

Ответ: 70