Задание 11 ЕГЭ: мощность алфавита по объёму памяти

Мощность алфавита по ограничению на объём памяти. Тема номера — информационный объём и мощность алфавита. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

При регистрации в системе каждому участнику выдаётся персональный код длиной 15 символов. Все коды составлены из символов одного алфавита. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый код — одинаковым и минимально возможным целым количеством байт.

Известно, что для хранения 4096 кодов потребовалось не менее 102 Кбайт памяти. Какое наименьшее количество символов может содержать алфавит, из которого составлены коды?

В ответе запишите только целое число.

Решение

При алфавите из N символов на символ нужно i = ⌈log₂N⌉ бит, на код — ⌈15·i / 8⌉ байт, на 4096 кодов — 4096 · ⌈15·i / 8⌉ байт. Объём растёт вместе с i, поэтому ищем подходящее i и переводим его в мощность алфавита: при i битах можно различить от 2ⁱ⁻¹ + 1 до 2ⁱ символов.

from math import ceil, log2

best = None
for N in range(2, 2 ** 16 + 1):
    i = ceil(log2(N))
    size = 4096 * ceil(15 * i / 8)      # байт
    if size >= 102 * 1024:
        best = N
        break
print(best)

Ответ: 8193.

Решить такую задачу — новый вариант с проверкой