Задание №11. Идентификаторы и объём памяти

Пароль или серийный номер состоит из символов. Для каждого символа выбирают двоичный код, а для всего номера выделяют целое число байт. В задании может требоваться общий объём памяти, длина номера, размер алфавита или объём дополнительных сведений. Основа решения одна: отделить код одного символа от памяти для одного номера и от памяти для всех записей.

От символа к записи

Мощность алфавита обозначается A. Если каждый символ кодируется одинаковым числом бит i, должно хватить разных двоичных кодов: 2^i\ge A. Выбирается наименьшее подходящее целое i.

Для 12 символов трёх бит мало: они дают только 2^3=8 кодов. Четырёх достаточно: 2^4=16. Поэтому каждый символ занимает 4 бита, даже если часть кодов не используется.

Если длина номера равна L символам, его код занимает Li бит. В одном байте 8 бит, поэтому память для одного номера:

B=\left\lceil\frac{Li}{8}\right\rceil байт.

Округление вверх относится к целому номеру. Каждый символ отдельно до байта не округляется. Если целое число байт выделяется каждому номеру, сначала находится B, затем результат умножается на количество номеров.

Пароль и дополнительные сведения

В задании EGE-11-0026 ↗ пароль содержит 23 символа из алфавита мощностью 12. На сведения о 297 пользователях выделено 13 068 байт. Помимо пароля, запись каждого пользователя содержит одинаковый объём дополнительных сведений. Требуется найти этот объём для одного пользователя.

1. Память для пароля

Для алфавита из 12 символов нужно 4 бита на символ. Значит, 23 символа занимают 23\cdot4=92 бита. Это 92/8=11{,}5 байта, поэтому под пароль выделяется 12 байт. В них 96 бит: 92 заняты кодом, ещё 4 остаются неиспользованными.

2. Память для всей записи

Общий объём включает и пароль, и дополнительные сведения. Все 297 записей одинакового размера, поэтому одна занимает 13\,068/297=44 байта.

3. Дополнительные сведения

Из 44 байт всей записи 12 приходятся на пароль. Остальное отведено дополнительным сведениям:

44-12=32 байта.

Обратная проверка восстанавливает исходный объём: 297\cdot(12+32)=13\,068 байт. Ответ: 32.

Общий объём без дополнительных полей

Если хранятся только идентификаторы, общий объём равен числу идентификаторов, умноженному на память для одного. В задании EGE-11-0037 ↗ разрешены 10 цифр и 500 специальных символов: A=510. Нужны 9 бит на символ, поскольку 256<510\le512.

Длина идентификатора — 113 символов. Его код занимает 113\cdot9=1017 бит, а выделенная память — 128 байт: 127 байт вмещают лишь 1016 бит. Для 65 536 идентификаторов потребуется 65\,536\cdot128=8\,388\,608 байт. В задании ответ нужен в Кбайт:

8\,388\,608/1024=8192 Кбайт.

В этих расчётах используются соотношения 1\text{ Кбайт}=1024\text{ байта} и 1\text{ Мбайт}=1024^2\text{ байт}. Перевод в единицы ответа выполняется после расчёта памяти для всех записей.

Обратная задача: длина номера

В задании EGE-11-0005 ↗ алфавит содержит 10 цифр и 15 специальных символов. На символ нужно 5 бит: 16<25\le32. Известно, что 947 номеров занимают более 6 Кбайт. Требуется минимальная длина номера.

Сначала условие переводится в байты: 6\cdot1024=6144. Если на номер выделено 6 байт, все номера занимают 947\cdot6=5682 байта: этого недостаточно для выполнения условия «более 6144». При 7 байтах получается 947\cdot7=6629 байт, и условие выполнено.

Теперь нужна наименьшая длина, при которой номер уже не помещается в 6 байт. Их вместимость — 6\cdot8=48 бит.

При 9 символах условие ещё не выполнено, при 10 — выполнено. Более короткий номер занимает не больше памяти, поэтому минимальная длина равна 10.

При поиске максимальной длины направление проверки меняется. Например, в EGE-11-0011 ↗ объём должен быть не более заданного. Подходящая длина проверяется вместе со следующей: увеличение на один символ должно уже нарушать ограничение.

Обратная задача: размер алфавита

В задании EGE-11-0003 ↗ 94 523 номера длиной 204 символа занимают не менее 12 Мбайт. Нужно найти минимальную мощность алфавита. Граница в байтах равна 12\cdot1024^2=12\,582\,912.

Проверяется сначала число бит на символ: оно определяет объём каждого номера. При 5 битах код занимает 204\cdot5=1020 бит, то есть 127,5 байта; выделяется 128 байт. При 6 битах получается 204\cdot6=1224 бита, ровно 153 байта. Для общего объёма каждый результат умножается на 94 523 номера.

Пять бит дают объём меньше требуемого; при ещё меньшем числе бит он только уменьшится. Шести бит достаточно. Но ответом должно быть количество символов, а не число бит. Пять бит позволяют закодировать 32 символа. Шестой бит впервые нужен для алфавита из 32+1=33 символов. Ответ: 33.

Для максимального алфавита берётся другая граница: при i битах помещается до 2^i символов. Такой вопрос поставлен в EGE-11-0004 ↗. Причины обеих границ разобраны в статье «Код символа и память для записи».

Возможные ловушки

• Неполный алфавит. В EGE-11-0047 ↗ учитываются цифры, прописные и строчные буквы, специальные символы: 10+26+26+6=68. Если забыть регистр, получится меньший алфавит и ошибочное число бит. Требование включить разные виды символов в пароль не меняет длину кода одного символа при заданном посимвольном кодировании.
• Округление в неверном месте. В EGE-11-0026 ↗ 92 бита пароля требуют 12 байт. Округление каждого символа до байта завысит объём, а округление общей суммы для всех паролей позволит использовать свободные биты соседней записи, чего условие не разрешает.
• Пароль вместо всей записи. В том же задании 44 байта — это пароль вместе с дополнительными сведениями. Если принять все 44 байта за пароль, потеряется искомая часть записи. Разделение «пароль + дополнительные сведения» сохраняется и в расчёте, и в проверке.
• Потерянная строгая граница. В EGE-11-0005 ↗ «более» означает >; равенство не подходит. В EGE-11-0003 ↗ «не менее» означает \ge. Округлённое десятичное частное не заменяет проверку исходного неравенства в целых байтах.
• Верхняя граница вместо нижней. Если минимально нужны 6 бит, мощность алфавита лежит от 33 до 64. Для минимального алфавита ответ 33, для максимального — 64. Подстановка 2^6 без учёта вопроса даёт неверный ответ в EGE-11-0003 ↗.