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

Переменная $M$ увеличивается на единицу при каждом делении $x$ на 6. Поэтому $M=3$ означает, что исходное число имеет ровно три цифры в шестиричной системе счисления.

Остатки от деления на 6 являются цифрами шестиричной записи числа. Если очередной остаток чётный, он умножается на $L$. Нулевая цифра дала бы $L=0$, поэтому для получения $L=16$ используются цифры 2 или 4.

На каждой итерации значение $x$ целочисленно делится на 2, поэтому цикл выполняется столько раз, сколько разрядов в двоичной записи исходного числа. Следовательно, $M=9$ означает, что число должно иметь 9 двоичных разрядов.$$M=9$$

Увеличение $L$ происходит тогда и только тогда, когда очередной остаток от деления на 2 равен 1. Поэтому $L$ — количество единиц в двоичной записи числа.$$L=5$$

При последовательном делении $x$ на $4$ алгоритм получает цифры числа $x$ в четверичной системе. Пусть $N$ — количество цифр, $A$ — их сумма, а $B$ — произведение.$$S=A+N,\quad P=B+N$$

По условию $S=9$ и $P=3$, поэтому $A+N=9$ и $B+N=3$. Так как $B\geq0$, имеем $N\leq3$.

Если $N$ чётное, к двоичной записи дописываются два нуля, поэтому результат равен $4N$.$$R = 4N$$

Если $N$ нечётное, к двоичной записи дописываются две единицы. Это означает умножение на $4$ и добавление числа $3$.$$R = 4N + 3$$

На каждой итерации число $x$ заменяется на результат целочисленного деления на 2. Поэтому $M$ равно длине двоичной записи исходного числа $x$.

При проверке остатка от деления на 2 переменная $L$ увеличивается для каждого нечётного остатка, то есть $L$ равно количеству единиц в двоичной записи числа.

От числа 17 до числа 1 нужно уменьшить значение на 16.$$17 - 1 = 16$$

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

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

Обозначим через $f(n)$ число программ перехода из $n$ в 9. Для $n>9$ выполняется рекуррентное соотношение $f(n)=f(n-1)+f(\lfloor n/2\rfloor)$, а $f(9)=1$. Последовательное вычисление даёт $f(30)=14$.$$f(30)=14$$

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

Посчитаем количество программ из 2 в каждое число до 9. Для числа $n$ учитываем переходы из $n-1$, из $n-2$ и, если $n$ кратно 3, из $n/3$.$$f(2)=1,\ f(3)=1,\ f(4)=2,\ f(5)=3,\ f(6)=6,\ f(7)=9,\ f(8)=15,\ f(9)=15+9+1=25$$

Из каждого текущего числа рассматриваем три возможных перехода: вычитание 1, вычитание 4 и деление на 3 с взятием целой части. Переходы, после которых получается 9, не учитываем.$$A(n)=n-1,\quad B(n)=n-4,\quad C(n)=\left\lfloor\frac{n}{3}\right\rfloor$$

Для каждого числа храним два значения: количество способов попасть в него без числа 9 и количество способов попасть в него с уже встречавшимся числом 15. При переходе в 15 способ переносится во вторую группу.

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

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

Обозначим через $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$$

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

Так как все команды увеличивают число, в каждой подходящей программе число 15 встречается один раз. Поэтому программу можно разделить на путь от 3 до 15 и путь от 15 до 25.$$N = N_{3\to15}\cdot N_{15\to25}$$

Для первой части применяем динамический подсчёт числа программ, исключая состояние 9. Получаем число допустимых путей от 3 до 15.

Из числа 5 в число 9 можно попасть только последовательным прибавлением единицы: $5 \to 6 \to 7 \to 8 \to 9$. Поэтому начальный участок программы единственный.$$N(5 \to 9)=1$$

Обозначим через $f(x)$ число способов попасть из 9 в $x$, не проходя через 27. Для остальных чисел используем динамическое программирование: последний шаг мог быть прибавлением 1, умножением на 2 или умножением на 3.$$f(x)=f(x-1)+[2\mid x]f\left(\frac{x}{2}\right)+[3\mid x]f\left(\frac{x}{3}\right)$$

Каждому числу сопоставим количество программ, которые переводят исходное число 111 в это число. Для числа 111 начальное количество программ равно 1.

Из каждого состояния добавляем переход по команде A: число увеличивается на 1. Также добавляем переход по команде B, если цифра в разряде десятков меньше цифры в разряде единиц; при этом две последние цифры меняются местами.

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

Последовательно вычисляя значения, получаем количество программ из 2 в 15:$$f(15)=f(13)+f(12)+f(5)=12+10+1=23$$

Пусть $f(n)$ — количество программ, переводящих число 2 в число $n$ без появления числа 14 в траектории. Начальное значение: $f(2)=1$, а для запрещённого числа полагаем $f(14)=0$.

Чтобы получить число $n$, последней могла быть команда прибавления 1, умножения на 2 или умножения на 3. Поэтому учитываются значения $f(n-1)$, $f(n/2)$ и $f(n/3)$ только при целочисленном делении.

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

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

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

Вычисляя значения от 3 до 10, получаем: $f(3)=1$, $f(4)=1$, $f(5)=1$, $f(6)=3$, $f(7)=4$, $f(8)=6$, $f(9)=9$, $f(10)=14$.

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

Для запрещённых чисел устанавливаем $f(9)=0$ и $f(15)=0$. Начальное значение: $f(3)=1$.

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

Для перехода из 30 в 8 вычисление рекуррентно даёт: $f(8)=1$, затем $f(9),\ldots,f(15)=1$, $f(16)=2$, и далее $f(30)=16$.