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

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

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

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

Кандидат 3 бит на символ:
Биты: 246 · 3 = 738.
Байты: 7388 → 93.
Границы округления: 92 · 8 = 736 — недостаточно; 93 · 8 = 744 — достаточно.
Общий объём: 703569 · 93 = 65431917 байт.
Условие «не более 80740352» выполнено.

Кандидат 4 бит на символ:
Биты: 246 · 4 = 984.
Байты: 9848 → 123.
Границы округления: 122 · 8 = 976 — недостаточно; 123 · 8 = 984 — достаточно.
Общий объём: 703569 · 123 = 86538987 байт.
Условие «не более 80740352» не выполнено.

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

Максимальная мощность: N = 2³ = 8.

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

Ответ: 8.