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

Последовательным буквам А, Б, В, Г соответствуют коды:$$\text{А}=00,\quad \text{Б}=01,\quad \text{В}=10,\quad \text{Г}=11$$

Кодируем последовательность ГБВА:$$\text{ГБВА}=11\ 01\ 10\ 00$$

Для выполнения условия Фано новое кодовое слово не должно быть началом другого кодового слова и не должно начинаться с уже существующего кодового слова.

Все кодовые слова длины 3 либо уже используются, либо являются префиксами существующих слов: 010, 011, 100 заняты, 101 является префиксом 1011, а слова, начинающиеся с 11, являются префиксами слов 1100, 1101, 1110 или 1111.

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

Два кодовых слова длины 2 можно выбрать как 00 и 01. Ни одно из них не является началом кодовых слов 101, 110 и 1000, и они не являются началами друг друга.$$l(\text{Г}) = 2,\quad l(\text{Д}) = 2$$

Изобразим известные кодовые слова как ветви двоичного дерева. Слово 10 занимает ветвь 10, а слова 0100, 0101 и 011 занимают ветви под началом 01.

Для четырёх оставшихся букв можно выбрать свободные кодовые слова 000, 001, 110 и 111. Ни одно из них не является началом другого и не начинается с уже занятого кодового слова.

Кодовые слова 00, 01 и 11 занимают три ветви двоичного дерева. Чтобы условие Фано выполнялось, неизвестные слова могут располагаться только в ветви 10.

Для трёх кодовых слов в ветви 10 минимально возможные длины — 3, 4 и 4. Более короткое слово длины 3 выгоднее назначить букве, которая встречается чаще всего.

Проверим возможные короткие слова в ветви, начинающейся с единицы. Слова $1$, $11$, $111$ использовать нельзя, поскольку они являются началами уже заданных кодовых слов.

Слово $1111$ также нельзя использовать: оно является началом кодового слова $11111$.

Кодовое слово для буквы У не может иметь длину 1: слова $0$ и $1$ являются началами уже заданных кодовых слов.

Проверим слова длины 2. Слово $00$ уже используется, а $01$, $10$ и $11$ являются началами существующих кодовых слов.

Проверим числа $N$, начиная с тех, которые могут дать результат, немного больший 133. Для числа, кратного 3, к троичной записи дописываются две последние цифры.

Для $N=15$ имеем $15_{10}=120_3$. Число $15$ делится на 3, поэтому дописываем две последние троичные цифры записи $20$ и получаем $12020_3$.

Проверим наибольшие подходящие значения $N$. Для $N=12$ двоичная запись имеет вид $1100_2$. Сумма цифр равна 2, поэтому дописываем справа 0: $11000_2$, затем заменяем два левых разряда на 10 и получаем $10000_2$.$$10000_2=16_{10}\leq19$$

Для следующего числа $N=13$ имеем $1101_2$. Сумма цифр равна 3, поэтому дописываем справа 1: $11011_2$. Первые два разряда уже равны 11, поэтому результат не меняется.$$11011_2=27_{10}>19$$

Если $N$ делится на 3, к его двоичной записи дописываются три последние цифры. Поэтому $R=8N+(N\bmod 8)$. При условии $R\leq208$ максимальное подходящее $N$, кратное 3, равно 24, и тогда $R\leq192$.

Если $N$ даёт остаток 1, дописывается двоичная запись числа 3, то есть $11_2$. Поэтому $R=4N+3$. При $R\leq208$ имеем $N\leq51$, но наибольшее $N\leq51$ с остатком 1 при делении на 3 — это $49$.

Для всех шестизначных двоичных записей максимальным числом является $N=63$. Его двоичная запись содержит шесть единиц, поэтому первый добавленный разряд равен $0$, а второй также равен $0.$$63_{10}=111111_2\ \longrightarrow\ 11111100_2=252_{10}$$

Полученный результат не превосходит 253, поэтому проверяем следующее число $N=64$.$$64_{10}=1000000_2$$

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

Для числа $N=11$ имеем $11_{10}=102_3$. Число 11 при делении на 3 даёт остаток 2.

Проверим значения $N$ начиная с наименьших. Для $N=7$ имеем $7=21_3$. Остаток от деления на 3 равен 1, поэтому дописываем троичную запись числа $1\cdot5=5$, то есть $12_3$.$$R=2112_3=68_{10}$$

Для $N=8$ имеем $8=22_3$. Остаток от деления на 3 равен 2, поэтому дописываем троичную запись числа $2\cdot5=10$, то есть $101_3$.$$R=22101_3=2\cdot3^4+2\cdot3^3+1\cdot3^2+1=220_{10}$$

Проверим значения $N$, дающие результаты около границы 180. Для $N=16$ имеем $16_{10}=121_3$, остаток при делении на 3 равен 1, поэтому дописываем $5_{10}=12_3$: $R=12112_3=176_{10}$.

Для $N=17$ имеем $17_{10}=122_3$, остаток равен 2, поэтому дописываем $10_{10}=101_3$. Получаем $R=122101_3=514_{10}$.

Для чисел, делящихся на 3, к двоичной записи дописываются три последние двоичные цифры. Поэтому значение результата вычисляется как $R=8N+(N\bmod 8)$.

Среди чисел, меньших 26 и делящихся на 3, наибольшее число — 24. Для него $24_{10}=11000_2$, поэтому $R=11000000_2=192$, что меньше 200.

При $k=45$ вычислим значение функции $G$:$$G(45)=2\cdot45+5=95$$

Цикл увеличивает $i$, пока $i^3<95$. При $i=4$ условие выполняется, а при $i=5$ уже нет:$$4^3=64<95,\quad 5^3=125\geq95$$

Для каждого индекса $n$ от 1 до 100 сначала вычисляется значение $A[n]=n-10$.

Затем вычисляется $B[n]=A[n]\cdot n$. Поскольку $n>0$, знак $B[n]$ совпадает со знаком $A[n]$.$$B[n]>0 \Longleftrightarrow n-10>0$$

Считываем все элементы последовательности и находим её минимальный элемент $m$.$$m = \min(a_1, a_2, \ldots, a_n)$$

Последовательно рассматриваем все пары соседних элементов $(a_i, a_{i+1})$ для $1 \le i < n$.

Последовательно сравниваем соседние элементы массива и учитываем только случаи, когда левый элемент меньше правого.$$A[1] < A[2],\ A[3] < A[4],\ A[4] < A[5],\ A[5] < A[6],\ A[6] < A[7],\ A[7] < A[8],\ A[8] < A[9]$$

После каждого такого сравнения элементы меняются местами, поэтому следующие сравнения нужно выполнять уже с изменённым массивом. Условие выполняется 7 раз.

При каждом проходе из большего значения вычитается меньшее, пока значения $m$ и $n$ не станут равными.$$m,n \to \gcd(81,48)$$

Выполняем последовательные вычитания: $81-48=33$, затем $48-33=15$, $33-15=18$, $18-15=3$.