ЕГЭ 11

По каналу связи передаются сообщения, содержащие только шесть букв: Т, Е, Н, С, И, В. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для букв известны: Т – 010, Е – 0100, Н – 1100, С – 01000, И – 0110, В – 1110. Как можно сократить код для буквы Н, чтобы сохранялось свойство однозначности декодирования? Если таких кодов несколько, в качестве ответа указать код наименьшей длины.

Примечание. Условие Фано означает, что соблюдается одно из двух условий. Либо никакое кодовое слово не является началом другого кодового слова, либо никакое кодовое слово не является окончанием другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

По каналу связи передаются сообщения из букв слова ГОРЕСТЬ. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв С, Е, Т, Ь используются кодовые слова 1, 0110, 01110, 011111, соответственно. Какое количество двоичных знаков потребуется для кодирования слова ГОРСТЬ, если известно, что оно закодировано минимально возможным количеством двоичных знаков? 

Примечание: под условием Фано понимается такой метод кодирования, при котором ни одно кодовое слово не является началом другого кодового слова. Такой способ кодирования позволяет получить однозначно декодируемый код.

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово СПОРТЛОТО кодируется как 10010100110011110000100. Какой код соответствует букве Л, если известно, что коды подбирались под минимальную длину заданного слова.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 17 символов и содержащий только символы из 19-символьного набора латинских букв: A, B, C, D, E, F, G, H, K, L, M, N, P, Q, R, S, T, Y, Z и 2 специальных арифметических знака: «+» и «*». В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование паролей, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно пароля, в системе хранятся дополнительные данные для каждого пользователя, для чего отведено 485 байт на одного пользователя.
Определите объём памяти (в Кбайт), необходимый для хранения полных сведений (паролей и дополнительных данных) о 4096 пользователях. В ответе запишите только целое число – количество Кбайт.

Вася решил закодировать персональные данные всех 1347 учеников всей школы. Для каждого ученика был сформирован ID из нескольких полей: номер класса, буква (а,б,в,г,д), пол, день и месяц рождения, номер имени по таблице имен (всего 103), номер фамилии по таблице фамилий (всего 733). Сперва Вася для каждого поля выделил минимальное количество байт. Затем попробовал закодировать все поля непрерывной битовой строкой и для каждого ID выделил минимальное количество байт. Сколько байт сэкономил Вася во втором случае для кодирования всех учеников школы?

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

Дата рождения состоит из дня (1-31), месяца (1-12) и года (1900-2500), при этом для хранения даты отводится битовая последовательность одинаковой минимальной длины для всех пользователей, которая представляет собой одно двоичное число. Номер паспорта представлен как строка из 12 цифр от 0 до 9, каждая из которых кодируется одинаковым и минимально возможным количеством бит. Известно, что для кодирования информации об одном пользователе выделяется целое, одинаковое для всех пользователей минимальное количество байт. Известно, что адрес проживания содержит символы из алфавита мощностью 32, при этом используется посимвольное кодирование, и каждый символ кодируется одинаковым и минимально возможным количеством бит.

Известно, что для хранения данных о 1316 пользователях понадобилось 27 Кбайт памяти. Найдите максимальную длину строки, которая может быть адресом пользователя.

Дана программа для исполнителя Редактор:

Известно, что исходная строка A содержала ровно два нуля – на первом и на последнем месте, а также поровну единиц и двоек. После выполнения данной программы получилась строка B, содержащая 47 единиц и меньше 70 двоек. Какое наибольшее количество двоек может быть в строке B?

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

1. заменить (v, w)

2. нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

Дана программа для исполнителя Редактор:

Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними были только цифры 1, 2 и 3. После выполнения данной программы получилась строка, содержащая 96 единиц, 36 двоек и 80 троек. Сколько цифр было в исходной строке?

Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл ПОКА условие последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно.

Дана программа для редактора:

Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 70 единиц, 56 двоек и 23 тройки. Сколько цифр было в исходной строке?