№ 5433 Джобс 21.12.22 (Уровень: Сложный)
В базе данных регистрационных данных о каждом пользователе хранятся следующие данные: дата рождения, номер паспорта и адрес проживания.
Дата рождения состоит из дня (1-31), месяца (1-12) и года (1900-2500), при этом для хранения даты отводится битовая последовательность одинаковой
минимальной длины для всех пользователей, которая представляет собой одно двоичное число. Номер паспорта представлен как строка из 12 цифр от 0 до 9, каждая из которых кодируется одинаковым и минимально возможным количеством бит. Известно, что для кодирования информации об одном пользователе выделяется целое, одинаковое для всех пользователей минимальное количество байт. Известно, что адрес проживания содержит символы из алфавита мощностью 32, при этом используется посимвольное кодирование, и каждый символ кодируется одинаковым и минимально возможным количеством бит.
Известно, что для хранения данных о 1316 пользователях понадобилось 27 Кбайт памяти. Найдите максимальную длину строки, которая может быть адресом пользователя.
Объяснение решения:
- Дата рождения:
День (1-31) → 5 бит
Месяц (1-12) → 4 бита
Год (1900-2500) → 601 вариант → 10 бит
Итого: 19 бит - Номер паспорта:
12 цифр × 4 бита = 48 бит - Адрес:
Каждый символ (из 32) → 5 бит
Ищем максимальное L, при котором общий объем ≤ 27 КБ - Расчет:
Для L=20: (19+48+100)/8=20.875 → 21 байт/запись
1316×21=27636 байт ≤ 27648 (27 КБ)
Для L=21: 27636+1316=28952 > 27648
Программа перебирает возможные длины адреса и находит максимальное значение (20), при котором объем данных не превышает 27 КБ.
Аналитически:
1. Определим размеры полей в битах
Дата рождения
- День: 1-31 → 5 бит (2⁵ = 32 ≥ 31)
- Месяц: 1-12 → 4 бит (2⁴ = 16 ≥ 12)
- Год: 1900-2500 → 601 значение (2500 - 1900 + 1) → 10 бит (2¹⁰ = 1024 ≥ 601)
- Итого: 5 + 4 + 10 = 19 бит
Номер паспорта
- 12 цифр, каждая 0-9 → 4 бита на цифру (2⁴ = 16 ≥ 10)
- Итого: 12 × 4 = 48 бит
Адрес проживания
- Алфавит из 32 символов → 5 бит на символ (2⁵ = 32)
- Длина адреса: L символов → 5L бит
2. Общий размер записи в битах
Общий размер=19 (дата)+48 (паспорт)+5L (адрес)=67+5L бит
3. Переведём в байты
Так как выделяется целое число байт:
Байт на запись=(67+5L) / 8
4. Общий объём данных
Для 1316 пользователей:
1316×((67+5L)/8)=27×1024 байт=27648 байт
5. Найдём максимальное L
Решим неравенство:
1316×((67+5L)/8)≤27648
(67+5L)/8≤27648/1316≈21
67+5L8≤21
67+5L≤168
5L≤101
L≤20.2
Так как L должно быть целым, максимальная длина адреса — 20 символов.
Проверка
При L = 20:
67+5×20=167 бит
167/8=21 байт
1316×21=27636 байт≤27648 байт
При L = 21:
67+5×21=172 бит
172/8=22 байт
1316×22=28952 байт>27648 байт
Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov
Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов!
А также ставьте лайк, пишите комментарии.
ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ
Тут все разборы собраны воедино