Задача к ЕГЭ по информатике на тему «автомобильные номера» №9

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Автомобильный номер состоит из уникальной строки и кода региона. Поступил заказ на всевозможные варианты номеров «АМ*?*АМ» для $250$ региона. Нумерация регионов начинается с $1$ . Код региона кодируется отдельно от уникальной строки минимально возможным числом бит. Условный знак «?» обозначает все заглавные буквы кириллицы, а «*» обозначет цифры от $0$ до $9$ включительно. Для кодирования кириллицы в номере используется русский алфавит из $33$ букв, который кодируется одинаковым минимально возможным числом бит. Для кодирования любой цифры в номере используется одинаковое минимально возможное число бит. Цифры и буквы в номере кодируются отдельно, а сам номер вместе с кодом региона кодируется минимально возможным количеством байт. Сколько байт информации нужно загрузить Петровичу в базу данных МВД о всех автомобильных номерах по шаблону «АМ*?*АМ» для $250$ региона?

Рассмотрим заказанный номер как «А «М «* «? «* «А «М»
Используется $5$ букв из кириллицы и $2$ цифры.

От $0$ до $9$ ровно $10$ цифр, поэтому придётся выделить хотя бы $4$ бита на кодирование цифры $3 4 2 = 8 < 10 < 2 = 16$ .

Один символ кириллицы, состоящий из $33$ букв, может быть закодирован не менее, чем $6$ битами, так как $25 = 32 < 33 < 26 = 64$ .

Итого, $(5 ⋅ 6 + 4 ⋅ 2) = 38$ бит требуется для кодирования ровно $1$ номера без региона с любыми допустимыми значениями на позициях «?»и «*»

Регион $250$ может быть закодирован не менее, чем $8$ битами, так как от $1$ до $256$ ровно $256$ чисел $7 8 2 = 128 < 250 < 2 = 256$ .

Получаем, что один номер с регионом можно закодированить с помощью $38 + 8 = 46$ бит. По условию каждый номер кодируется минимально возможным количеством байт, следовтельно, $6 ⋅ 8 = 48 > 46 » class=»math» src=»/images/inform/reshen/reshen-1269-20.svg» width=»auto»> можно закодировать номер <img decoding=$ -ю байтами.

Но в задаче нас просят найти количество информации, которое нужно для кодирования всех возможных вариантов номеров, где вместо «?»может стоять любая буква из кириллицы, а вместо «*»– любая цифра от $0$ до $9$ .

Комбинаторными вычислениями получаем, что всего возможных вариантов номеров может быть $33 ⋅ 10 ⋅ 10 = 3300$

Тогда Петровичу придётся внести

$6 ⋅ 3300 = 19800$ байт информации о номерах из заказа.

Ответ: 19800