Задание 22 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

Проверим числа, начиная с наименьших кандидатов. Для $N=18$ имеем $18_{10}=10010_2$. Сумма цифр равна 2, поэтому сначала дописывается 0, затем сумма цифр снова равна 2 и дописывается 0.$$10010_2 \to 100100_2$$

Получаем $100100_2=36_{10}$, поэтому результат для $N=18$ не больше 76.

На каждой итерации переменная $x$ заменяется на результат целочисленного деления на $8$, поэтому $M$ равно количеству цифр исходного числа в восьмеричной системе счисления. Условие $M=3$ означает, что исходное число имеет вид $abc_8$, где…

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

После первого цикла значение $x$ увеличивается на 10 до тех пор, пока не станет больше 100. Обозначим число выполнений цикла через $K_1$, а получившееся значение — через $y$.$$y=x+10K_1,  101\le y\le110$$

Второй цикл вычитает из $y$ число 6 $K_2$ раз. Поэтому после него остаётся остаток $z$ от деления $y$ на 6: $y=6K_2+z$, где $0\le z\le5$.$$L=z+K_1=7,\quad M=z+K_2=21$$

Для чётного $N$ к двоичной записи приписываются слева единица и справа нуль. Проверим четырёхразрядные записи чётных чисел.$$1000_2 \to 11000_2=24,\quad 1010_2 \to 110100_2=52,\quad 1100_2 \to 111000_2=56$$

Число $56$ превышает 52. Меньшие подходящие значения из этого случая не превышают 52.

Проверяем числа $N$ по возрастанию. Для $N=19$ двоичная запись имеет вид:$$19_{10}=10011_2$$

Сумма цифр записи $10011$ равна 3. Остаток от деления на 2 равен 1, поэтому дописываем справа цифру 1:$$10011\to100111$$

Переведём границу в двоичную систему: $101_{10}=1100101_2$. Проверим числа, начиная с наименьших, у которых результат может превысить 101.

Для $N=24$ имеем $24_{10}=11000_2$. Сумма цифр равна 2, поэтому после двух шагов получаем $110000_2=48_{10}$, что не больше 101.

При каждом делении $x$ на 2 переменная $M$ увеличивается на 1. Поэтому $M$ равно числу разрядов двоичной записи исходного числа. Условие $M = 8$ означает, что число должно быть восьмиразрядным.

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

Для каждого процесса определяем самое раннее время начала: оно равно нулю для независимых процессов, а для зависимого процесса — максимальному времени окончания всех его предшественников.

Вычисляем время окончания каждого процесса как сумму его времени начала и длительности выполнения.

Для чётного числа $N$ к его двоичной записи слева приписывается единица, а справа — нуль.

Проверим первое подходящее чётное число. Для $N=10$ двоичная запись имеет вид $1010$.

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

Для каждого процесса определяем интервал его выполнения в миллисекундах: от найденного времени начала до времени начала плюс длительность процесса минус 1.

На каждой итерации число заменяется на результат целочисленного деления на $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)$$