Разбор всех задач с kompege.ru Ч.24

Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов быстрее!

№ 5061 (Уровень: Сложный)

Система мониторинга формирует и отправляет специальные сообщения, в которые могут входить только следующие символы: латинские буквы (26 заглавных и 26 строчных), цифры от 0 до 9, пробел. Количество символов в сообщении может быть любым.

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

Система отправила четыре сообщения по 35 символов каждое и пять сообщений по 27 символов. При этом всего было передано более 320 байт. Какое наименьшее число байтов может содержать заголовок сообщения? В ответе запишите только целое число – количество байтов.

Объяснение решения:

1. Определяем мощность алфавита (63 символа) и бит на символ (6 бит)
2. Вычисляем размер сообщений:
   35 символов → 35×6=210 бит → 27 байт
   27 символов → 27×6=162 бит → 21 байт
3. Ищем минимальный заголовок, при котором общий объем > 320 байт:
   При заголовке 11 байт: 4×(11+27) + 5×(11+21) = 312 байт (не подходит)
   При заголовке 12 байт: 4×(12+27) + 5×(12+21) = 321 байт (подходит)

Таким образом, минимальный размер заголовка составляет 12 байт.

Аналитически:

1. Определим мощность алфавита и бит на символ

Алфавит содержит:

• 26 заглавных букв
• 26 строчных букв
• 10 цифр
• 1 пробел
  Итого: 26 + 26 + 10 + 1 = 63 символа

Для кодирования 63 символов нужно:

log⁡2(63)=6 бит на символ

2. Размер сообщения в байтах

Каждое сообщение кодируется целым числом байтов:

Размер сообщения=(6×кол-во символов)/8 байт

Для сообщений разной длины:

• 35 символов:

(6×35)/8=26.25=27 байт

• 27 символов:

(6×27)/8=20.25=21 байт

3. Общий объём данных

Пусть заголовок занимает H байт. Тогда общий объём:

4×(H+27)+5×(H+21)>320

4H+108+5H+105>320

9H+213>320

9H>107

H>11.8

Так как H должно быть целым, минимальное возможное значение: H = 12 байт

4. Проверка

При H = 12:

4×(12+27)+5×(12+21)=4×39+5×33=156+165=321>320

При H = 11:

4×38+5×32=152+160=312 (меньше 320)

Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov

А также ставьте лайк, пишите комментарии.

ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ

Тут все разборы собраны воедино