Задание 11. Информатика. ЕГЭ. Поляков-5913
- Просмотры: 42
- Изменено: 11 апреля 2025
(Е. Джобс) В базе данных регистрационных данных о каждом пользователе хранятся следующие данные: дата рождения, номер паспорта и адрес проживания. Дата рождения состоит из дня \((1-31),\) месяца \((1-12)\) и года \((1900-2500),\) при этом для хранения даты отводится битовая последовательность одинаковой минимальной длины для всех пользователей, которая представляет собой одно двоичное число. Номер паспорта представлен как строка из \(12\) цифр от \(0\) до \(9,\) каждая из которых кодируется одинаковым и минимально возможным количеством бит. Известно, что для кодирования информации об одном пользователе выделяется целое, одинаковое для всех пользователей минимальное количество байт. Известно, что адрес проживания содержит символы из алфавита, состоящего из \(32\) символов, при этом используется посимвольное кодирование, и каждый символ кодируется одинаковым и минимально возможным количеством бит. Известно, что для хранения данных о \(1316\) пользователях понадобилось \(27\) Кбайт памяти. Найдите максимальную длину строки, которая может быть адресом пользователя.
Решение:
На одного пользователя выделяется \(\lfloor 27 \cdot 2^{10} / 1316 \rfloor = 21\) байт. Дату рождения минимальные образом можно закодировать так: день месяца кодируем \(5\) битами \((2^4 = 16 < 31 < 32 = 2^5).\) Сам месяц кодируем \(4\) битами \((2^3 = 8 < 12 < 16 = 2^4).\) Год можно закодировать числом от \(0\) до \(600.\) Оно получается как разность года рождения и числа \(1900.\) Это число можно закодировать \(10\) битами \((2^9 = 512 < 600 < 1024 = 2^{10}).\) Итак, дата рождения кодируется \(5 + 4 + 10 = 19\) битами. Паспорт кодируем \(4 \cdot 12 = 48\) битами. Поэтому на адрес остаётся \(21 \cdot 8 - 19 - 48 = 101\) бит. Так как алфавит, состоящий из \(32\) символов кодируется минимум \(5\) битами, получаем, что строка адреса может состоять максимум из \(\lfloor 101 / 5 \rfloor = 20\) символов.
Ответ: \(20\)