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

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

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

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

Кандидат 6 бит на символ:
Биты: 204 · 6 = 1224.
Байты: 12248 → 153.
Границы округления: 152 · 8 = 1216 — недостаточно; 153 · 8 = 1224 — достаточно.
Общий объём: 94523 · 153 = 14462019 байт.
Условие «не менее 12582912» выполнено.

Кандидат 5 бит на символ:
Биты: 204 · 5 = 1020.
Байты: 10208 → 128.
Границы округления: 127 · 8 = 1016 — недостаточно; 128 · 8 = 1024 — достаточно.
Общий объём: 94523 · 128 = 12098944 байт.
Условие «не менее 12582912» не выполнено.

Нужная граничная длина кода: b = 6. Такое минимальное число бит требуется для алфавита из N символов, когда N больше 2⁵ = 32, но не превосходит 2⁶ = 64.

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

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

Ответ: 33.