Решение: Сначала определим, к какому наименьшему числу мы можем применять только одну команду. Нам даны команды +1, +2 и *2, очевидно, что наименьшее число — 11. Число 11 мы не можем умножить на 2 и не можем прибавить к нему 2, единственное, что можно сделать — прибавить 1. Рассмотрим это на графе:
Из числа 11 мы можем получить 12 только прибавив единицу. Количество программ, для получения 12 из числа 11 — 1, оно обведено кружком, чтобы не запутаться в числах.
Рассмотрим число 10:
Из числа 10 мы можем получить 11 (прибавив 1) и 12 (прибавив 2). То есть из числа 10 существует две программы для получения числа 12.
Рассмотрим число 9:
Из числа 9 мы можем получить числа 10 и 11. Из числа 10 существует 2 программы для получения 12, из числа 11 — одна программа. Общее количество программ для получения 12 из числа 9 — три.
Рассмотрим число 8:
Из числа 8 мы можем получить 9 и 10. Из числа 9 существует три программы, из числа 10 — две программы, общее количество программ — 5.
Рассмотрим число 7:
Из числа 7 можно получить числа 8 и 9, из числа 8 существует пять программ, из числа 9 — три программы, общее количество программ — 8.
Рассмотрим число 6:
Обратите внимание, число 6 мы можем умножить на 2. Из числа 6 можно получить числа 7, 8, 12. Из числа 7 существует 8 программ, из числа 8 — 5 программ, число 12 конечное, то есть мы можем указать для него одну программу. Общее количество программ — 14.
Рассмотрим число 5:
Из числа 5 мы можем получить числа 6, 7 и 10. Из числа 6 существует 14 программ, из числа 7 — 8 программ, из числа 10 — 2 программы. Общее количество программ — 24.
Рассмотрим число 4, последнее:
Из числа 4 мы можем получить числа 5, 6 и 8. Из числа 5 существует 24 программы, из числа 6 — 14 программ, из числа 8 — 5 программ. Общее количество программ, с помощью которых можно получить число 12 из числа 14 — 43.
Ответ: 43
