Задание EGEINFBB5645: Объём информации, пароли и кодировки

Пусть L — длина номера, b — число бит на символ. Код номера занимает L · b бит. Размер P одного номера — наименьшее целое число байт, которое вмещает эти биты, то есть результат округления L · b8 вверх. Общий объём B = K · P, где K = 75600.

Граница памяти: 16 Мбайт = 16 · 1048576 = 16777216 байт.
Требование условия: общий объём более 16777216 байт. Равенство допускается только в формулировках «не более» и «не менее».

При увеличении числа бит на символ округлённый размер записи не уменьшается. Поэтому для доказательства минимума достаточно найти допустимую границу и проверить соседнее меньшее целое значение.

Кандидат 8 бит на символ:
Биты: 248 · 8 = 1984.
Байты: 19848 → 248.
Границы округления: 247 · 8 = 1976 — недостаточно; 248 · 8 = 1984 — достаточно.
Общий объём: 75600 · 248 = 18748800 байт.
Условие «более 16777216» выполнено.

Кандидат 7 бит на символ:
Биты: 248 · 7 = 1736.
Байты: 17368 → 217.
Границы округления: 216 · 8 = 1728 — недостаточно; 217 · 8 = 1736 — достаточно.
Общий объём: 75600 · 217 = 16405200 байт.
Условие «более 16777216» не выполнено.

Нужная граничная длина кода: b = 8. Такое минимальное число бит требуется для алфавита из N символов, когда N больше 2⁷ = 128, но не превосходит 2⁸ = 256.

Минимальная мощность: N = 2⁷ + 1 = 129.

Проверка: выбранная граница удовлетворяет исходному условию после округления каждой записи, соседняя граница — нет. Из монотонности общего объёма следует, что все ещё меньшие значения также не подходят. Значит, требуемый экстремум достигнут.

Ответ: 129.