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

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

Последовательно получаем: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=2$, $f(6)=3$, $f(7)=3$, $f(8)=5$, $f(9)=5$, $f(10)=7$, $f(11)=7$, $f(12)=10$, $f(13)=10$, $f(14)=13$.

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

Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для $n$ от 4 до 9 учитываем последние команды: прибавление 1, прибавление 2 и умножение на 3.$$f(n)=f(n-1)+f(n-2)+[3\mid n]f(n/3)$$

Введём динамику: количество способов получить число складывается из количества способов получить его из предыдущего числа командой 1 и из числа, вдвое меньшего, командой 2.

Так как траектория должна содержать число 15, разбиваем каждую программу на две части: путь от исходного числа 2 до числа 15 и путь от числа 15 до числа 45.

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

Для участка от 3 до 10 подсчётом по последней команде получаем последовательность количества путей: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$, $f(9)=17$, $f(10)=30$.$$N(3,10)=30$$

Введём $f(n)$ — количество программ, переводящих исходное число 101 в число $n$. Для исходного числа $f(101)=1$.

Переход по команде A возможен из числа $n-1$, поэтому он добавляет $f(n-1)$ способов.

Введём динамическое подсчитывание количества программ, ведущих из одного числа в другое. Для попадания в число $x$ последняя команда могла быть одной из трёх: прибавление 2, умножение на 2 или прибавление 3.

Отдельно подсчитываем программы перехода от исходного числа 2 к числу 10 и программы перехода от числа 10 к числу 21. По рекуррентному подсчёту получаем по 9 программ для каждого участка.

Чтобы траектория содержала число 10, программа состоит из пути от 30 до 10 и пути от 10 до 1. Эти части можно комбинировать независимо.

Обозначим через $f(n)$ число способов попасть из $n$ в 10. Используем рекуррентное соотношение $f(n)=f(n-1)+f(\lfloor n/2 \rfloor)$ и получаем $f(30)=12$.

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

Последовательно вычисляя значения, получаем: $f(1)=1$, $f(2)=1$, $f(3)=3$, $f(4)=4$, $f(5)=7$, $f(6)=12$, $f(7)=19$, $f(8)=31$, $f(9)=53$.

Поскольку все команды увеличивают число, число 12 в траектории может встретиться только один раз. Поэтому число искомых программ равно произведению числа программ из 2 в 12 и числа программ из 12 в 21.$$N = N_{2\to12} \cdot N_{12\to21}$$

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

Общая величина увеличения числа должна составить $20 - 1 = 19$.

Пусть команда «прибавить 2» выполнена $a$ раз, а команда «прибавить 5» — $b$ раз. Тогда $2a + 5b = 19$.

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

Последнее слагаемое учитывается только для чётных $n$. Получаем значения до числа 11:$$f(4)=1,\ f(5)=1,\ f(6)=2,\ f(7)=3,\ f(8)=6,\ f(9)=9,\ f(10)=16,\ f(11)=25$$

Введём динамическое программирование: для каждого числа считаем количество программ, которые приводят к нему. Последний шаг в такую точку мог быть выполнен командами $+1$, $\times 2$ или $\times 3$.

Посчитаем количество способов попасть из 1 в 11. Для числа $n$ учитываются переходы из $n-1$, $n/2$ и $n/3$, если соответствующие значения являются целыми.

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

Последовательно получаем значения: $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$.

Поскольку каждая команда увеличивает число, программа, содержащая в траектории числа 9 и 11, сначала должна попасть в 9, затем в 11.

Посчитаем динамически число способов попасть из 3 в каждое число с помощью команд «+1», «+2» и «×2». Для чисел от 3 до 9 получаем: $1, 1, 2, 4, 6, 11, 17$. Значит, $N(3 \to 9)=17$.$$N(x)=N(x-1)+N(x-2)+[x\ \text{чётно}]N\left(\frac{x}{2}\right)$$

Обозначим через $f(n)$ число способов получить число $n$ из 4, не попадая в 6. Для числа 6 полагаем $f(6)=0$, так как траектория не должна содержать 6.

Последовательно получаем значения: $f(4)=1$, $f(5)=1$, $f(6)=0$, $f(7)=1$, $f(8)=2$, $f(9)=3$, $f(10)=6$, $f(11)=9$, $f(12)=15$, $f(13)=24$, $f(14)=40$, $f(15)=64$.

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

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

Обозначим через $f(n)$ количество программ, переводящих число 2 в число $n$ без попадания в 11. Для числа 2 имеем $f(2)=1$.

Число $n$ можно получить командой A из $n-1$, командой B из $n/2$ при чётном $n$ и командой C из $\sqrt{n}$, если $n$ является полным квадратом.

Общее уменьшение числа при переходе от 23 к 2 равно 21.$$23 - 2 = 21$$

Пусть команда «вычесть 2» выполнена $a$ раз, а команда «вычесть 5» — $b$ раз. Тогда $2a+5b=21$. Возможны два решения: $(a,b)=(8,1)$ и $(a,b)=(3,3)$.

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

Количество способов получения каждого числа вычисляем рекуррентно: число способов попасть в $x$ равно сумме количеств способов попасть в $x-2$, $x-3$ и $x/2$, если $x$ чётно. При подсчёте программ от 10 до 25 способы, проходящие через 17…

От числа 1 до числа 21 нужно увеличить значение на 20.$$21 - 1 = 20$$

Пусть $a$ — количество команд «прибавить 2», а $b$ — количество команд «прибавить 5». Тогда$$2a + 5b = 20$$