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

По данным файла для каждого процесса определяем наиболее раннее время начала: оно равно нулю для независимых процессов, а для зависимого процесса — максимальному времени окончания его предшественников.$$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}$$

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

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

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