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

Алгоритм последовательно выделяет цифры числа $x$, складывает их в переменную $a$ и находит максимальную цифру в переменной $b$.$$a = \text{сумма цифр},\quad b = \text{максимальная цифра}$$

Требуется, чтобы сумма цифр была равна $11$, а максимальная цифра — $6$. Наименьшее возможное количество цифр — две: $5$ и $6$.

Дописать справа два двоичных разряда означает умножить исходное число на $2^2 = 4$ и прибавить значение дописанных разрядов.$$R = 4N + \text{значение дописанных разрядов}$$

Если $N$ чётное, дописывается $01$, поэтому $R = 4N + 1$. Если $N$ нечётное, дописывается $10$, поэтому $R = 4N + 2$.

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

Для каждого процесса вычисляем самое раннее время завершения. Для независимого процесса оно равно его длительности. Для остальных процессов к максимальному времени завершения предшественников прибавляем длительность текущего процесса.$$T(B)=\max\limits_{A\in Pred(B)}T(A)+d(B)$$

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

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

Проверим числа, начиная с 98, представляя их в двоичной системе. Для числа 102 получаем двоичную запись $1100110$.

Удаляем последние два разряда. Исходная запись числа $N$ должна быть $11001$, то есть $N = 25$.

Приписывание двух разрядов справа эквивалентно умножению двоичного числа на $4$.

Для нечётного $N$ приписывается $01$, поэтому $R=4N+1$. Для чётного $N$ приписывается $10$, поэтому $R=4N+2$.

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

Переменная $L$ увеличивается тогда, когда текущее значение $x$ чётное. Для получения $L = 6$ первые шесть значений должны быть чётными, а последнее — нечётным.

Пусть исходное число представлено в виде $x_0=9q+r$, где $q$ — частное, а $r$ — остаток от деления на 9. После цикла $L=q$, а $x=r$.$$x_0=9q+r,\quad 0\leq r<9$$

После цикла переменная $M$ получает значение остатка: $M=r$. Если $r<q$, выполняется условие, и значения меняются местами: итоговые $L=r$, $M=q$.

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

Для каждого процесса строим интервал выполнения по формуле: если процесс начинается на миллисекунде $s$ и длится $t$ миллисекунд, то он выполняется на миллисекундах от $s$ до $s+t-1$.

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

Если $N$ нечётное, дописывается двоичный суффикс $01$, поэтому $R=4N+1$. Если $N$ чётное, дописывается суффикс $10$, поэтому $R=4N+2$.

На каждой итерации алгоритм получает последнюю цифру числа $x$ с помощью операции остатка от деления на 10 и приписывает её в конец числа $R$.$$d = x \bmod 10,\quad R = 10R + d$$

После этого последняя цифра числа $x$ удаляется целочисленным делением на 10. Поэтому алгоритм записывает цифры исходного числа в обратном порядке.

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

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

Каждое выполнение цикла заменяет $x$ на результат целочисленного деления на $8$. Поэтому $M$ равно количеству цифр числа в восьмеричной системе счисления. При $M=3$ число имеет вид $(abc)_8$, где $a\ne0$.

Величина $L$ умножается на остаток от деления на $8$ только тогда, когда текущая цифра нечётная. Следовательно, $L$ равно произведению нечётных цифр восьмеричной записи.

Каждое выполнение цикла увеличивает $M$ на единицу, а затем заменяет $x$ на целую часть от деления на $8$. Поэтому $M$ равно количеству цифр исходного числа в восьмеричной системе. При $M = 3$ число имеет вид трёхзначного восьмеричного…$$x = (abc)_8$$

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

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

Для каждого процесса вычислим раннее время завершения. Для независимого процесса оно равно его длительности, а для зависимого — сумме его длительности и максимального времени завершения всех зависимостей.$$T_i = t_i + \max_{j \in D_i} T_j$$

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

Множитель добавляется только для чётных текущих значений $x$. Остаток $x \bmod 8$ при этом является очередной цифрой восьмеричной записи числа.

Приписывание двух нулей справа в двоичной записи умножает число на $4$. Поэтому для чётного $N$ результат равен $4N$.$$R=4N$$

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

Дописание двух разрядов справа умножает исходное число на $4$. Для чётного $N$ добавляется двоичный суффикс $01$, поэтому $R=4N+1$.

Для нечётного $N$ добавляется суффикс $10$, поэтому $R=4N+2$.

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

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

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

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