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

Просмотров 6 Комментарии 0

Вступая в марафон Школково по информатике, вы становитесь клоном АР. Каждому клону присваивается уникальный номер и два счётчика: кол-во пробников, которые клон закрабил, и кол-во пробников, которые клон уничтожил. В системе произошёл сбой и АР потерял информацию о том, сколько максимум клонов он может держать в своей голове. АР помнит, что для подсчёта количества используются числа от 0 до 16000 включительно. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Вся информация на чипе занимает минимальное целое число байт. Также у него остался доступ к базе прошлого года весом 512 КБайт с 32768 клонами. Помогите вспомнить АР потерянную информацию. В ответе запишите максимальное количество бит, которое выделено для хранения личного кода клона АР.

Чтобы закодировать два счётчика от 0 до 16000, потребуется не менее $14 ⋅ 2 = 28$ бит (умножаем на 2, потому что это два отдельных блока), так как $213 = 8192 < 16001 < 214 = 16384$ .

Вся информация на чипе занимает минимальное целое число байт. Тогда вся информация об одном клоне АР занимает $512⋅1024- 32768 = 16$ байт.

Пусть i – количество бит, которое выделено для хранения личного кода клона АР. Тогда $28+i 8 ≤ 16$ , $i = 100$ бит.

Ответ: 100