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

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

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

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

Условие $x \bmod 2 \ne 0$ выполняется для нечётных промежуточных значений, то есть для единичных разрядов двоичной записи. Поэтому $L$ равно количеству единиц.

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

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

По данным прилагаемого файла для каждого процесса последовательно определяем самое раннее время начала: независимые процессы начинают выполняться с первой миллисекунды, а зависимые — после завершения всех указанных предшественников.$$s_B = \max_{A \in Pred(B)} f_A + 1$$

Для каждого процесса вычисляем последнюю миллисекунду выполнения по формуле: время окончания равно времени начала плюс длительность минус единица.$$f_B = s_B + t_B - 1$$

Результат 621 может быть получен только из двух произведений 6 и 21, записанных в одном из двух порядков.

Пусть цифры исходного числа равны $a$, $b$, $c$. Тогда произведения имеют вид $ab$ и $bc$. Общая цифра $b$ должна быть общим делителем чисел 6 и 21, поэтому $b = 3$.

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

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

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

По условию алгоритм выводит сначала 7, а затем 3, поэтому сумма цифр и произведение цифр должны удовлетворять равенствам:$$A+N=7,\quad B+N=3$$

Проверим минимальные числа, превышающие 83. Число 84 имеет двоичную запись $1010100_2$, но первые пять разрядов дают $10101_2$, а по правилу должны дописаться разряды $1$ и $0$, поэтому результатом было бы $1010110_2$.

Число 85 имеет двоичную запись $1010101_2$ и также не соответствует правилу: после записи $10101_2$ должны дописываться $1$ и $0$, а не $0$ и $1$.

Пусть $n = K_1$ — число выполнений первого цикла. После него значение переменной равно $x_0 + 10n$ и превышает 100.

Пусть $r$ — значение переменной после второго цикла. Тогда $0 \le r < 8$, а $L = r + n = 12$, поэтому $r = 12 - n$.

В цикле из исходного числа $x$ вычитают 6, а переменную $L$ увеличивают на 1. Поэтому после завершения цикла $L$ — целая часть частного от деления $x$ на 6, а $M$ — остаток.$$x = 6L + M,\quad 0 \leq M < 6$$

Если после цикла $M < L$, значения меняются местами: первым печатается остаток, вторым — частное. Чтобы получить 3 и 5, должны выполняться $M=3$ и $L=5$.$$x = 6 \cdot 5 + 3 = 33$$

По данным файла для каждого процесса определяем наиболее раннее время начала: оно равно нулю для независимых процессов, а для зависимого процесса — максимальному времени окончания его предшественников.$$t_{\text{нач}}(B)=\max\limits_{A\to B}t_{\text{ок}}(A)$$

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

Число $R$ должно быть больше $63$, то есть его двоичная запись должна иметь не менее семи разрядов. Поэтому запись числа $N$ должна иметь не менее пяти разрядов.

Минимальное пятизначное двоичное число — $N=10000_2$. Сумма его цифр равна $1$, поэтому первый добавленный разряд равен $1$.

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

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

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

Для независимого процесса его время завершения равно времени выполнения: $T_i = t_i$.

При добавлении двух разрядов справа двоичное число умножается на 4. Затем к нему прибавляется значение приписанной пары.$$R=4N+1 \text{ при нечётном }N;\quad R=4N+2 \text{ при чётном }N$$

Для нечётного числа нужно найти наименьшее нечётное $N$, для которого результат больше 74:$$4N+1>74\Rightarrow N>18{,}25\Rightarrow N=19$$

На каждом шаге алгоритм получает очередную цифру числа $x$ в троичной системе счисления: это остаток от деления на 3. Обозначим количество троичных цифр через $N$, их сумму через $A$, а произведение через $B$.$$S = A + N = 8,\quad P = B + N = 4$$

Рассмотрим возможные значения $N$. При $N = 1$ произведение цифр должно быть 3, что невозможно для троичной цифры. При $N = 2$ сумма цифр должна быть 6, что также невозможно. При $N = 3$ произведение должно быть 1, поэтому все цифры равны…$$A = 8 - N,\quad B = 4 - N$$

Дописание двух разрядов справа увеличивает двоичное число в четыре раза, после чего добавляется значение новых разрядов.$$R = 4N + 1 \text{ при нечётном } N;\quad R = 4N + 2 \text{ при чётном } N$$

Для нечётного $N$ должно выполняться $4N + 1 < 89$, поэтому $N < 22$. Наибольшее нечётное $N$ равно 21.$$R = 4 \cdot 21 + 1 = 85$$

Число $51$ в двоичной системе счисления записывается как $110011_2$. Искомое число должно иметь двоичную запись не меньше этой и быть минимальным.

Для четырёхзначной записи $N$ проверяем записи, начинающиеся с $1100$. При $N=1100_2$ сумма цифр равна $2$, поэтому добавляются разряды $0$ и $0$: получается $110000_2=48$, что меньше 51.

Обозначим цифры исходного трёхзначного числа через $a$, $b$, $c$. Число $621$ должно быть получено из двух произведений, записанных друг за другом: $6$ и $21$.$$a \times b = 6,\quad b \times c = 21$$

Оба произведения содержат общий множитель $b$. Общий делитель чисел $6$ и $21$ равен $3$, поэтому берём $b = 3$.$$a = \dfrac{6}{3} = 2,\quad c = \dfrac{21}{3} = 7$$

Дописание двух двоичных разрядов справа умножает исходное число $N$ на 4.$$R=4N+a$$

Если $N$ нечётное, дописывается двоичный суффикс $01$, поэтому $a=1$ и $R=4N+1$. Если $N$ чётное, дописывается суффикс $10$, поэтому $a=2$ и $R=4N+2$.$$R=\begin{cases}4N+1, & N\text{ нечётное}\\4N+2, & N\text{ чётное}\end{cases}$$