Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов!
№ 4468 Джобс 15.06.2022 (Уровень: Сложный)
При регистрации в компьютерной системе каждому объекту присваивается
идентификатор содержащий только десятичные цифры и символы из 1234-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Известно, что для хранения 65 536 идентификаторов понадобилось не более 2050 КБайт. Укажите максимально допустимую длину идентификатора пользователя.
Аналитически:
1. Определим количество бит на символ
Алфавит содержит:
- 10 цифр (0-9)
- 1234 специальных символа
Общий размер алфавита: 10 + 1234 = 1244 символа
Количество бит на символ:
log₂1244 = 11 бит (так как 2¹⁰ = 1024 < 1244 < 2048 = 2¹¹)
2. Рассчитаем максимальную длину идентификатора
Дано:
- 65,536 идентификаторов
- Общий объем ≤ 2050 КБ = 2050 × 1024 = 2,099,200 байт
Пусть L - длина идентификатора (в символах), тогда:
Размер одного идентификатора в битах: 11 × L
В байтах: (11 × L)/8
Общий объем:
65,536 × (11 × L)/8 ≤ 2,099,200
Решим неравенство:
(11 × L)/8 ≤ 2,099,200 / 65,536 ≈ 32.03
Значит, (11 × L)/8 ≤ 32
Максимальное L, удовлетворяющее условию:
(11 × L)/8 ≤ 32
11 × L ≤ 256
L ≤ 256/11 ≈ 23.27
Проверим L = 23:
(11 × 23)/8 = 253/8 = 31.625 → 31.625 = 32 байта
Общий объем: 65,536 × 32 = 2,097,152 байт (≤ 2,099,200)
Проверим L = 24:
(11 × 24)/8 = 264/8 = 33 → 33 байта
Общий объем: 65,536 × 33 = 2,162,688 байт (> 2,099,200)
3. Ответ
Максимально допустимая длина идентификатора: 23 символа
Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov
А также ставьте лайк, пишите комментарии.
ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ
Тут все разборы собраны воедино