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

В цикле из числа $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$ означает, что в двоичной записи числа ровно пять единиц.

Алгоритм последовательно выделяет цифры числа $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$.