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

На каждой итерации алгоритм получает последнюю цифру числа $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$ равно произведению нечётных цифр восьмеричной записи числа.

Каждая итерация заменяет $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$$