Решения заданий ФИПИ ЕГЭ по информатике: «Алгоритмы и исполнители» — с ответами

Рассмотрим сначала программы, переводящие число 38 в число 16. Обозначим через $f(n)$ количество способов попасть из $n$ в 16. Для каждого числа учитываем переходы $n \to n-2$ и $n \to \lfloor n/2 \rfloor$.$$f(n)=f(n-2)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)$$

Последовательное вычисление значений от 16 до 38 даёт: $f(18)=1$, $f(20)=1$, $f(22)=1$, $f(24)=1$, $f(26)=1$, $f(28)=1$, $f(30)=1$, $f(32)=2$, $f(34)=2$, $f(36)=3$, $f(38)=3$. Значит, из 38 в 16 можно попасть 3 способами.

Так как обе команды уменьшают число, любую подходящую программу можно разделить в момент появления числа 14 на две независимые части: путь от 30 до 14 и путь от 14 до 1.$$N(30 \to 1\text{ через }14)=N(30 \to 14)\cdot N(14 \to 1)$$

Для каждого числа последовательно подсчитываем количество способов попасть из него в нужное целевое число. При этом учитываются переходы $n \to n-2$ и $n \to \lfloor n/2 \rfloor$.

Обозначим через $f(n)$ число программ, переводящих число 3 в число $n$. Для получения $n$ последняя команда может быть прибавлением 1, прибавлением 2 или умножением на 2.$$f(n)=f(n-1)+f(n-2)+\begin{cases}f(n/2),& n\text{ чётно},\\0,& n\text{ нечётно}. \end{cases}$$

Последовательно получаем значения до числа 8: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$. Значит, существует 11 способов попасть из 3 в 8.

Для подсчёта числа программ введём $f(n)$ — количество способов получить число $n$ из числа 2. Переходы к числу $n$ могут выполняться командами A, B и C.$$f(n)=f(n-1)+f(n-3)+\begin{cases}f(n/3),& n\ \text{кратно}\ 3,\\0,&\text{иначе}\end{cases}$$

При подсчёте значений до 16 исключаем число 12: количество путей, проходящих через 12, принимаем равным нулю. Получаем последовательность значений от 2 до 16: $1, 1, 1, 2, 4, 5, 7, 12, 17, 24, 0, 17, 41, 43, 60$.$$f(16)=60$$

Так как все команды увеличивают число, сначала в траектории встречается 9, затем 11. Поэтому программу можно разделить на три независимых участка.$$N=N_{3\to9}\cdot N_{9\to11}\cdot N_{11\to13}$$

Пусть $f(n)$ — число программ, переводящих число 3 в число $n$. Последней командой могут быть прибавление 1, прибавление 2 или умножение на 3.$$f(n)=f(n-1)+f(n-2)+f(n/3)$$

Обозначим через $f(n)$ число программ, переводящих число $n$ в число 1. Для числа 1 программа может быть пустой, поэтому $f(1)=1$.$$f(1)=1$$

Для остальных чисел последняя команда может быть либо вычитанием 1, либо целочисленным делением на 2.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$

Рассмотрим числа как вершины графа. Из каждой вершины проводим переход по команде A к числу, увеличенному на 1.

Переход по команде B добавляем только тогда, когда цифра десятков меньше цифры единиц; при этом две младшие цифры меняются местами.

Все команды увеличивают число, поэтому число 14 в траектории встречается не более одного раза. Подсчитаем количество путей от 3 до 14, запрещая число 8.$$f(n)=f(n-1)+f(n-2)+f(n/2),\quad f(8)=0$$

Последовательное вычисление даёт количество путей от 3 до 14 без прохождения через 8:$$f(14)=72$$

Посчитаем количество программ, переводящих число 2 в число 6. Обозначим через f(n) число способов получить n из 2.$$f(n)=f(n-1)+f(n-2)+f(n/3)\text{ при }3\mid n$$

Последовательно получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=f(5)+f(4)+f(2)=3+2+1=6.

Посчитаем количество программ, переводящих число 2 в число 11. Для числа $n$ учитываем последние команды «прибавить 2», «прибавить 3» и, при чётном $n$, «умножить на 2». Получаем $f(11)=10$.$$f(n)=f(n-2)+f(n-3)+[n\text{ чётно}]f\left(\frac n2\right)$$

Аналогично посчитаем количество программ, переводящих число 11 в число 22. Получаем $g(22)=10$.

Пусть $f(n)$ — количество допустимых программ, переводящих число $n$ в число 3. Базовое значение: из числа 3 можно завершить программу без выполнения команд.$$f(3)=1$$

Для каждого числа $n$ учитываем три последние команды: A переводит в $n-1$, B — в $n-2$, C — в $\lfloor n/3\rfloor$.$$f(n)=f(n-1)+f(n-2)+f(\lfloor n/3\rfloor)$$

Обозначим через $f(n)$ количество программ, переводящих число $n$ в число 1. Для $n>1$ последняя команда может быть A или B, поэтому используем рекуррентный подсчёт.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor),\quad f(1)=1$$

Последовательно вычисляя значения, получаем:$$f(1),\ldots,f(10)=1,2,3,5,7,10,13,18,23,30$$

Так как все команды уменьшают число, траектория обязательно проходит через 13 ровно один раз. Поэтому количество подходящих программ равно произведению числа способов попасть из 19 в 13 и числа способов попасть из 13 в 2, избегая числа 7.

Обозначим через $f(n)$ число способов попасть из $n$ в 13. Для $n>13$ учитываем переходы $n\to n-1$, $n\to n-4$ и $n\to \lfloor n/3\rfloor$. Число 7 не может быть промежуточным состоянием.$$f(13)=1,\quad f(14)=1,\quad f(15)=1,\quad f(16)=1,\quad f(17)=2,\quad f(18)=3,\quad f(19)=4$$

Обозначим через $f(n)$ количество программ, переводящих число 1 в число $n$. Последняя команда может быть прибавлением 1 или умножением на 2.$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n$$

Последовательно вычисляем количество программ до числа 10: $f(1)=1$, $f(2)=2$, $f(3)=2$, $f(4)=4$, $f(5)=4$, $f(6)=6$, $f(7)=6$, $f(8)=10$, $f(9)=10$, $f(10)=14$.$$f(10)=f(9)+f(5)=10+4=14$$

Так как обе команды уменьшают число, траектория может содержать число 12 только один раз. Поэтому любую подходящую программу можно однозначно разделить на путь от 30 до 12 и путь от 12 до 1.

Обозначим через $f(n)$ количество способов получить число 12 из числа $n$. Для $n > 12$ имеем $f(n)=f(n-2)+f(\lfloor n/2\rfloor)$, поскольку последней выполненной командой может быть A или B. Последовательное вычисление даёт $f(30)=3$.$$f(30)=f(28)+f(15)=3$$

Так как все команды увеличивают число, сначала траектория проходит через 8, затем через 10.$$N = N_{2\to 8} \cdot N_{8\to 10} \cdot N_{10\to 12}$$

Обозначим через $f(n)$ количество программ, переводящих 2 в $n$. Для чисел от 2 до 8 получаем: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=3$, $f(6)=6$, $f(7)=9$, $f(8)=15$.$$f(n)=f(n-1)+f(n-2)+f(n/3)\text{, если }3\mid n$$

Так как обе команды уменьшают число, траектория может содержать число 13 не более одного раза. Поэтому программы можно однозначно разделить на часть от 30 до 13 и часть от 13 до 1.

Подсчитаем количество способов попасть из 30 в 13. Возможны последовательные вычитания, а также переходы делением на 2 из чисел 30, 29, 28, 27 и 26. Динамическим подсчётом получаем 6 способов.$$N_{30\to13}=6$$

Так как все команды увеличивают число, числа 10 и 12 в траектории встречаются именно в указанном порядке. Поэтому искомое количество программ является произведением числа способов пройти три участка.$$N(4,14;10,12)=N(4,10)\cdot N(10,12)\cdot N(12,14)$$

Посчитаем количество способов попасть из 4 в 10. Для каждого числа учитываются переходы из чисел на 1 и 2 меньше, а также из числа вдвое меньшего, если оно целое.$$N(4,10)=16$$

Обозначим через $f(n)$ число программ, переводящих число $n$ в число 1. Для каждого $n > 1$ последняя команда является либо вычитанием 1, либо делением на 2.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor),\quad f(1)=1$$

Последовательно вычисляя значения, получаем число программ от 9 до 1:$$f(2)=2,\ f(3)=3,\ f(4)=5,\ f(5)=7,\ f(6)=10,\ f(7)=13,\ f(8)=18,\ f(9)=23$$

Так как все команды увеличивают число, число 9 в траектории достигается ровно один раз. Поэтому программы можно разбить на две независимые части: от 2 до 9 и от 9 до 17.

Обозначим через $f(n)$ число программ, переводящих 2 в $n$. Для последнего шага возможны команды A, B и C, поэтому $f(n)=f(n-1)+f(n-2)+f(n/2)$ для чётного $n$, а для нечётного $n$ последнее слагаемое отсутствует.