Тапсырма 22 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

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

Условие $L=5$ означает, что в двоичной жазбалар числа должно быть ровно пять единиц.

Проверим числа, большие 55, начиная с минимальных. Число 55 имеет двоичную запись $110111_2$, поэтому ближайшие кандидаты имеют записи $111000_2$, $111001_2$, $111010_2$.

Для записи $111010_2$ отбросим последние два разряда. Получаем исходную запись $1110_2$, то есть $N=14$.

При каждой итерации алгоритм заменяет $x$ на $x \mathbin{//} 8$, поэтому остатки $x \bmod 8$ являются цифрами исходного числа в восьмеричной системе. Число итераций $M=3$ означает, что у числа ровно три восьмеричные цифры.

В произведение $L$ входят только чётные восьмеричные цифры. Их произведение должно быть равно $12$. Из возможных чётных цифр $0, 2, 4, 6$ подходит набор $2$ и $6$, так как $2 \cdot 6 = 12$.

Переведём искомое число в двоичную систему и последовательно применим правило алгоритма.$$112_{10}=1110000_2$$

Для записи $1110000$ сумма цифр равна $3$, поэтому первый дописываемый разряд равен $1$. После его добавления сумма цифр становится равной $4$, поэтому второй разряд равен $0$.

Дописание двух нулей справа в двоичной записи означает умножение числа на $4$. Если $N$ чётное, результат равен $4N$.$$R=4N$$

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

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

Процессы, не связанные отношением зависимости и доступные одновременно, запускаются параллельно. Это обеспечивает минимальное время окончания всех процессов.

Дописание двух разрядов справа умножает исходное двоичное число на $4$. Поэтому для чётного $N$ результат равен $4N$, а для нечётного — $4N+3$.$$R(N)=\begin{cases}4N, & N\text{ чётное},\\4N+3, & N\text{ нечётное}.\end{cases}$$

Для нечётного числа требуется $4N+3>134$, откуда $N>32{,}75$. Минимальное нечётное натуральное число, удовлетворяющее этому условию, равно $33$.

При последовательном целочисленном делении $x$ на 4 остатки являются цифрами записи числа $x$ в четверичной системе счисления. Число итераций $N$ равно количеству цифр этой записи.

Пусть цифры четверичной записи числа $x$ равны $d_1, d_2, \ldots, d_N$. Тогда после цикла $S=d_1+d_2+\ldots+d_N+N=7$, а $P=d_1d_2\ldots d_N+N=3$.

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

Величина $x\bmod 8$ — очередная цифра восьмеричной записи. Она включается в произведение $L$ только тогда, когда текущая часть числа чётна, то есть очередная восьмеричная цифра чётна.

Представим процессы в виде ориентированного графа: дуга направлена от процесса-предшественника к зависящему от него процессу.

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

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

Остаток 1 при делении на 2 соответствует единице в очередном разряде двоичной записи. Поэтому $L=4$ означает, что в двоичной записи должно быть ровно четыре единицы.$$L=4$$

Приписывание двух разрядов справа означает умножение числа $N$ на $2^2=4$.

Если $N$ нечётное, приписывается $01$, поэтому $R=4N+1$. Условие $4N+1<96$ даёт $N<23{,}75$. Максимальное нечётное $N$ равно 23, тогда $R=4\cdot23+1=93$.

Обозначим через $p$ остаток от деления суммы единиц в двоичной записи числа $N$ на 2. Первый дописанный разряд равен $p$.

После добавления первого разряда чётность суммы цифр становится $p+p=0$, поэтому второй дописанный разряд равен 0.

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

Условие $M=7$ означает, что двоичная запись числа состоит из семи цифр, то есть начинается с единицы.

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

Если последняя цифра числа нечётная, она умножается на $L$. Следовательно, $L$ равно произведению нечётных цифр восьмеричной записи числа.$$L=15$$

Пусть после первого цикла значение переменной $x$ равно $y$, а остаток после второго цикла — $r$. После первого цикла $y$ принимает значение от 101 до 110, а $K_1$ — количество прибавлений 10.

Во втором цикле из $y$ вычитают 6 до тех пор, пока не получится число $r$ от 0 до 5. Поэтому $y=6K_2+r$.

Чтобы получить результат больше $100$, достаточно рассматривать пятиразрядные двоичные записи: после добавления двух разрядов получится шестизначное число.

Проверяем числа начиная с $16$. Для $N=24$ имеем $24_{10}=11000_2$. Сумма цифр равна $2$, поэтому дважды дописывается ноль: $110000_2=48_{10}$.

Число $R$ должно быть больше 127, поэтому его двоичная запись должна содержать не менее восьми разрядов. Для минимального подходящего числа рассматриваем восьмиразрядные записи.$$127_{10}=1111111_2$$

Первые шесть разрядов записи $R$ являются двоичной записью числа $N$. Чтобы получить минимальное число, начинаем с минимальной восьмиразрядной записи, превышающей $01111111_2$.

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

Переменная $b$ накапливает сумму цифр исходного числа.

Число $396$ в двоичной системе счисления имеет вид $110001100_2$. Проверяем следующие числа, отбрасывая у их двоичных записей последние два разряда.

Для числа $402$ получаем $402_{10}=110010010_2$. Тогда исходная жазба числа $N$ равна $1100100_2$.