Задание 13 ЕГЭ по информатике · 07D82E

1. Пусть f(n) — число программ, переводящих число n в число 3 и не содержащих в траектории чисел 13 и 14. Для числа 3 учитываем пустую последовательность команд: f(3)=1.
f(3)=1

2. Последняя команда программы может быть A, B или C. Поэтому для остальных разрешённых значений n количество программ равно сумме количества программ для чисел n−1, n−2 и ⌊n/3⌋.
f(n)=f(n−1)+f(n−2)+f(⌊n/3⌋)

3. Так как траектория не должна содержать числа 13 и 14, устанавливаем f(13)=f(14)=0. Последовательное вычисление даёт:
f(15)=2, f(16)=4, f(17)=8, f(18)=15, f(19)=26

4. Для исходного числа 20 получаем:
f(20)=f(19)+f(18)+f(6)=26+15+3=44