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

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

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

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

Для зависимого процесса вычисляем самое раннее начало: оно следует после окончания самого позднего из процессов-зависимостей. Если последний из них заканчивается на миллисекунде $k$, процесс начинается на миллисекунде $k+1$.

За одну итерацию значение $x$ заменяется на результат целочисленного деления на $8$. Поэтому $M$ равно числу цифр исходного числа в восьмеричной системе счисления.

Условие $M=3$ означает, что $64 \leqslant x \leqslant 511$.

Цикл вычитает из $x$ число $9$, пока результат не станет меньше $9$. Поэтому после цикла $L=q$, а оставшееся значение $M=r$, где $x=9q+r$ и $0\leq r<9$.$$x=9q+r$$

Если $r<q$, алгоритм заменяет $M$ на $q$, а $L$ на $r$. Чтобы получить сначала $5$, а затем $8$, можно взять $q=8$, $r=5$.

По данным файла для каждого процесса определяем время начала. Если процесс зависит от нескольких процессов, его запуск возможен после завершения самого позднего из них.$$t_{start}(B)=\max_{A\in Dependencies(B)}(t_{start}(A)+t(A))$$

Для каждого процесса записываем интервал его выполнения $[t_{start}, t_{start}+t]$ и объединяем все моменты начала и окончания процессов.

Рассмотрим чётное число $N$ с шестизначной двоичной записью. После добавления слева единицы и справа нуля получаем число вида $1\,\text{bin}(N)\,0$.$$R = 2^{7} + 2N = 128 + 2N$$

Требуется, чтобы $R > 225$, поэтому $128 + 2N > 225$, откуда $N > 48{,}5$. Наименьшее подходящее чётное число — $N=50$.$$R = 128 + 2 \cdot 50 = 228$$

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

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

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

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

Переведём число 114 в двоичную систему счисления:$$114_{10}=1110010_2$$

Удалим два последних разряда. Получаем предполагаемую исходную запись числа $N$:$$1110010_2\to11100_2$$

Проверим числа, начиная с наименьших возможных кандидатов около границы. Для $N=21$ двоичная запись имеет вид $10101$.$$10101_2 \to 101011_2 \to 1010110_2 = 86_{10}$$

Результат для $N=21$ не больше 89, поэтому проверяем следующее число $N=22$.$$22_{10}=10110_2$$

В цикле из числа $x$ вычитают 9, пока это возможно. Поэтому после цикла $L$ — частное, а оставшееся значение $M$ — остаток от деления $x$ на 9: $x=9L+r$, где $M=r$.

Если остаток меньше частного, алгоритм присваивает $M=L$, а $L=r$. Чтобы получить вывод 4, затем 5, возможен случай $r=4$, $L=5$.

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

Минимальной подходящей двоичной записью является $1100110_2$.$$1100110_2 = 1\cdot2^6 + 1\cdot2^5 + 0\cdot2^4 + 0\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 0\cdot2^0$$

Для каждого процесса по данным файла определяем все его непосредственные зависимости.

Самые ранние моменты запуска процессов вычисляем рекурсивно: независимый процесс запускается с начала отсчёта, а зависимый — после завершения всех процессов, от которых он зависит.$$start(B)=\max_{A\in dependencies(B)} finish(A)$$

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

Для каждого процесса вычислим наиболее раннее время начала. Оно равно нулю для независимых процессов, а для остальных определяется окончанием наиболее позднего процесса-зависимости:$$start(B)=\max_i finish(A_i)$$

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

Следовательно, сумма цифр искомого числа должна быть равна $10$, а наибольшая цифра — $7$. Чтобы число было наименьшим, проверим двузначные числа: при десятке $1$ нужна цифра $9$, но тогда максимальная цифра будет $9$; при десятке $2$…

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

Если $N$ чётное, дописывается $01_2=1$, поэтому $R=4N+1$. Наибольшее чётное $N$, для которого $R<125$, равно $30$: $R=4\cdot30+1=121$.

Для каждого процесса по таблице из файла вычисляем самое раннее время начала. Если процесс не имеет зависимостей, он начинается с 1-й миллисекунды. Для зависимого процесса начало определяется окончанием последнего из процессов-зависимостей.$$start(B)=\max\limits_{A\in dependencies(B)}(start(A)+duration(A))$$

Для каждого процесса строим интервал выполнения: если он начинается на миллисекунде s и длится d миллисекунд, то выполняется на миллисекундах s, s+1, \ldots, s+d-1.$$finish(B)=start(B)+duration(B)-1$$

В цикле переменная $a$ увеличивается на каждую цифру числа, поэтому после завершения алгоритма $a$ равна сумме цифр числа $x$.$$a = \sum d_i$$

Переменная $b$ принимает значение очередной цифры, если она больше текущего значения $b$. Поэтому в конце $b$ равна максимальной цифре числа $x$.$$b = \max(d_i)$$

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

Так как $M = 3$, запишем число в виде $x = \overline{abc}_8$, где $a \ne 0$, а $a$, $b$, $c$ — цифры от 0 до 7.

На каждой итерации алгоритм делит $x$ на $2$ с отбрасыванием остатка. Количество итераций $M$ равно количеству цифр в двоичной записи исходного числа.

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