Задание 11

На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 963-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 2000 серийных номеров отведено не более 693 Кбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число.

Теория

Необходимо знать принципы кодирования текстовой информации. 

Кодирование текстовой информации заключается в определении мощности алфавита (множества всех символов) и определение минимального числа бит - i (сколько бит позволяют закодировать алфавит из целого количества символов N, для этого решаем уравнение аналогичное уравнению при кодировании графической информации

и находим i - должно быть целое число и 2ⁱ ≥ N, а 2^i-1 < N. Например N = 80, тогда 2⁶ < 80 ≤ 2⁷ и i = 7 (для кодирования алфавита из 80 символов понадобится 7 бит). Далее умножаем число i на количество символов в идентификаторе или пароле и получаем необходимое количество бит для хранения текста. В задачах для хранения обычно отводится целое количество байт, поэтому полученное число разделите на 8 и результат округлите до ближайшего большего целого.

Решение

В данной задаче нам неизвестна длина серийного номера. Обозначим её за k. Найдём мощность алфавита. Он содержит десятичные цифры (10), 52 латинские буквы (с учётом регистра - строчные и заглавные) и символы из 963-символьного специального алфавита - 10 + 52 + 963 = 1025.

Решая двойное неравенство 2^i-1 < 1025 ≤ 2ⁱ получаем i = 11 бит (Полезно помнить степени числа 2, хотя бы до 2¹²). Тогда длина идентификатора 11•k/8 - округленное до ближайшего большего целого в байтах. Для хранения 2000 идентификаторов отведено не более 693 Кбайт памяти.

693 Кбайт/2000 = 693•1024/2000 = 354,816 байт ≈ 354 байт

Здесь округлили в меньшую сторону, иначе если округлить в большую сторону, то в итоге превысим 693 Кбайт памяти. Это целое количество байт для хранения одного идентификатора. Далее решаем уравнение

11•k = 354•8

Обе части уравнения в битах. Получаем k = 257,45(45) - количество символов в идентификаторе может быть только целым! Значит результат - длина идентификатора 257 символов. Легко проверить: 11•257/8=353,357, округляем в большую сторону до целого и получаем 354. Далее 354•2000/1024 = 691,4 Кбайт < 693. 

Ответ

257 (Время не более 5 минут)