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

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

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

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

Кандидат 11 бит на символ:
Биты: 196 · 11 = 2156.
Байты: 21568 → 270.
Границы округления: 269 · 8 = 2152 — недостаточно; 270 · 8 = 2160 — достаточно.
Общий объём: 564895 · 270 = 152521650 байт.
Условие «не менее 152043520» выполнено.

Кандидат 10 бит на символ:
Биты: 196 · 10 = 1960.
Байты: 19608 → 245.
Границы округления: 244 · 8 = 1952 — недостаточно; 245 · 8 = 1960 — достаточно.
Общий объём: 564895 · 245 = 138399275 байт.
Условие «не менее 152043520» не выполнено.

Нужная граничная длина кода: b = 11. Такое минимальное число бит требуется для алфавита из N символов, когда N больше 2¹⁰ = 1024, но не превосходит 2¹¹ = 2048.

Минимальная мощность: N = 2¹⁰ + 1 = 1025.

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

Ответ: 1025.