Каждое изделие, изготовленное на предприятии, получает уникальный код, состоящий из 22 символов. Каждый символ кода может быть латинской буквой (только строчной), десятичной цифрой или специальным символом из дополнительного набора. Используется посимвольное кодирование, каждый символ кодируется одинаковым минимально возможным числом бит, а для хранения каждого кода в целом отводится одинаковое минимально возможное число байт.
Известно, что для хранения списка из 4000 кодов выделено не более 100 Кбайт. Какое наибольшее количество специальных символов может входить в дополнительный набор символов?
Имеем: M = 26 + 10 + x, где M — мощность алфавита, x — количество спец. символов. Вес одного символа алфавита в битах можно найти по формуле M = 2i. По условию задачи N = 22, n = 4000. Следовательно, объём одного кода получается: V1 = i · N. Весь объём: V = n · V1 = n · i · N ⩽ 100 Кбайт. Так как n · i · N ⩽ 819200 бит, получаем, что
Итак, M = 2i = 512, следовательно, 26 + 10 + x = 512, x = 476.
Ответ: 476.
Приведём решение Юрия Красильникова на языке Python.
for k in range(100,1,-1): # длина кода символа в битах
bits = k*22 # длина серийного номера в битах
bytes = bits//8
if bits%8 != 0: bytes+=1 # длина серийного номера в байтах
if bytes*4000 <= 100*1024: # если 4000 номеров занимают не более 100К:
print(2**k-26-10)
break