Информатика ЕГЭ — решения заданий ФИПИ с ответами

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

Остаток от деления на $8$ равен очередной последней цифре восьмеричной записи. Если эта цифра чётная, она прибавляется к $L$.

При каждом делении $x$ на $8$ алгоритм отбрасывает последнюю восьмеричную цифру. Поэтому число $M$ равно количеству цифр исходного числа в восьмеричной системе счисления.

Условие $M=3$ означает, что исходное число имеет вид $abc_8$, где $a\ne0$. Величина $L$ равна сумме тех цифр $a$, $b$, $c$, которые являются нечётными.

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

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

По таблице из файла строим граф зависимостей процессов. Каждый процесс можно начать сразу после завершения всех процессов, от которых он зависит.

Рассчитываем расписание с минимальным временем окончания всех процессов: время начала процесса определяется максимальным временем окончания его предшественников.

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

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

По таблице из файла строится граф зависимостей процессов. Процесс можно запустить только после завершения всех указанных для него процессов-предшественников.

Для каждого процесса вычисляются самое раннее время начала и время окончания. Независимые процессы запускаются одновременно, а зависимые — после завершения необходимых предшественников.$$t_{\text{нач}}(B)=\max_{A\in P(B)}t_{\text{кон}}(A)$$

На каждой итерации значение $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$$

Представим процессы в виде ориентированного графа: из процесса $A$ ведём ребро в процесс $B$, если $B$ зависит от $A$.

Для независимого процесса время завершения равно его длительности. Для зависимого процесса время завершения вычисляется как сумма его длительности и максимального времени завершения всех предшественников.$$T_B = t_B + \max(T_{A_1}, T_{A_2}, \ldots)$$

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

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

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

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

Каждая дизъюнкция равна нулю, значит все её конъюнкции равны нулю. Из условий $x_i \land \neg x_{i+1}=0$ следует $x_i \le x_{i+1}$, поэтому последовательность $x$ неубывает.$$x_1 \le x_2 \le \ldots \le x_6$$

Из условий $\neg y_i \land y_{i+1}=0$ следует $y_i \ge y_{i+1}$, поэтому последовательность $y$ невозрастает.$$y_1 \ge y_2 \ge \ldots \ge y_6$$

Так как обе команды уменьшают число, любая программа, траектория которой содержит 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$$

Чтобы дизъюнкция была тождественно истинной, не должно существовать таких $x$ и $y$, при которых все её части ложны.$$\neg(x + 2y < A) \land \neg(y > x) \land \neg(x > 20)$$

Все части одновременно ложны при условиях:$$x + 2y \geq A,\quad y \leq x,\quad x \leq 20$$

Поскольку все команды увеличивают число, числа 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$$

Функция $F$ равна нулю, только если каждый член дизъюнкции равен нулю.$$\neg x = 0,\quad y=0,\quad \neg z \wedge w=0$$

Из условия $\neg x=0$ получаем $x=1$, а из условия $y=0$ — $y=0$. Поэтому столбец с постоянными единицами — четвёртый, а столбец с постоянными нулями — третий.

Во второй строке значения в первых трёх столбцах равны $1$, $0$, $0$, а значение функции равно 0. Поэтому все три части дизъюнкции должны быть равны 0. Это возможно, если неизвестное значение в четвёртом столбце равно 1, а столбцы имеют…

Проверим вторую строку при $w=1$, $z=0$, $y=0$, $x=1$:$$(\neg 1 \land \neg 0) \lor (1 \equiv 0) \lor \neg 1 = 0 \lor 0 \lor 0 = 0$$

Дизъюнкция ложна только тогда, когда ложны все три высказывания:$$x \geq A,\quad y \geq A,\quad x + 2y \leq 50$$

При условиях $x \geq A$ и $y \geq A$ наименьшее возможное значение выражения $x + 2y$ достигается при $x = A$ и $y = A$:$$x + 2y \geq A + 2A = 3A$$

Из каждого текущего числа рассматриваем три возможных перехода: вычитание 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 способ переносится во вторую группу.