Ах, эти загадочные пароли и байты! Представьте себе: вы регистрируетесь в системе, а вам выдают пароль из 9 символов, каждый из которых взят из набора «В, У, З, Н, А, Б, Ю, Д, Ж, Е, Т». Если бы это был заголовок к фильму ужасов — «Проклятие 11 символов», но нет – это всего лишь наша задача. И вот представьте: для хранения информации о 23 пользователях потребовалось ровно 713 байт.
Казалось бы, что тут сложного? Но нет!
Нужно понять, сколько байт отведено на дополнительные данные каждого пользователя.
Кстати говоря про минимальное количество бит на символ — это как пытаться упаковать кота в коробку поменьше. Все хотят сэкономить место, но кот (или в нашем случае информация) не всегда согласен с этим. В наборе у нас 11 символов — значит сколько бит нужно? Ну конечно же минимум такой степени двойки, чтобы вместить все эти буквы.
2^3=8 слишком мало (влезет только 8 символов), а 2^4=16 уже подходит! Значит каждый символ кодируется четырьмя битами.
Пароль из 9 символов — значит всего 36 бит или 4.5 байта. Но нельзя хранить половину байта – так что округляем до пяти. Вот где начинается веселье: если пароль занимает пять байт (минимальное целое число), то остаток памяти идет на дополнительные сведения.
Аналогично и в следующей задаче: у нас теперь пароль из 15 символов с латинскими буквами верхнего и нижнего регистра плюс цифры – итого 26+26+10 =62 варианта для каждого символа.
Как тут не вспомнить анекдот про программиста: «Почему ты используешь столько разных символов? Чтобы никто не смог угадать твой пароль!» А он отвечает: «Нет-нет!
Просто мне нравится разнообразие». Для кодирования таких символов понадобится минимум шесть бит (2^6=64). Значит на весь пароль уйдет 15*6=90 бит или около 12 с половиной байт (опять же округляем вверх до целого числа).
А дальше еще дополнительные сведения… В итоге для хранения данных о 17 пользователях ушло ровно 255 байт – ну чисто как в сказке про золотую рыбку: «Отдай мне число байт – и я скажу тебе дополнительные данные».
Третья история еще смешнее – здесь нам дают пароль из десяти символов с набором из букв НЕПРИДУМАЛ (да-да, сама судьба подсказывает!), цифр и специальных знаков вроде #,$,@,_,% . Интересно представить себе администратора системы: «Ну давайте добавим спецсимволы для разнообразия! Пусть пользователи ломают голову над паролями!» И вот тут начинается магия чисел: известно, что память на пароль ровно в полтора раза меньше памяти на дополнительные данные.
Это как если бы у вас было полтора пирога и вы решили поделиться с другом так хитро… В итоге задача просит посчитать минимальное количество байт для хранения данных о всех пользователях.
В четвертой истории мы уже переходим к более продвинутым паролям длиной в одиннадцать символов – каждый может быть либо буквой латинского алфавита в двух начертаниях (то есть заглавная или строчная), либо цифрой от нуля до девяти или одним из забавных знаков типа пробела или скобочек. Это напоминает попытку запомнить пароль после вечеринки: «Что там было? Ах да — большой А потом маленькая b потом пробел…» К тому же электронный адрес содержит только строчные буквы и пару специальных знаков (@ и .), максимум двадцать символов. На хранение информации о двадцати пользователях ушло ровно шестьсот байт – прямо праздник оптимизации!