Решение автокодом -> Определите максимальную возможную мощность алфавита...

№ 18180 (Уровень: Средний)

В медицинском учреждении каждой медицинской карточке пациента присваивают уникальный идентификатор, состоящий из 23 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 500 000 идентификаторов отведено не более 21 Мбайта памяти. Определите максимальную возможную мощность алфавита, который используется для составления идентификаторов. В ответе запишите только число.

from math import ceil

for b in range(30, 0, -1):
    idx = ceil(23 * b / 8)
    if 500_000 * idx <= 21 * 1024 * 1024:
        print(2 ** b)
        break

Разберём код построчно.

Шаг 1. Подключаем функцию ceil

from math import ceil

Функция ceil() округляет число в большую сторону до ближайшего целого.

Например:

• ceil(10.1) = 11

• ceil(10.9) = 11

• ceil(10) = 10

Она нужна потому, что память выделяется только целыми байтами. Если для хранения требуется 43,2 байта, то на самом деле нужно выделить 44 байта.

Шаг 2. Перебираем количество бит на один символ

for b in range(30, 0, -1):

Переменная b — это количество бит, которым кодируется один символ идентификатора.

Функция range(30, 0, -1) создаёт последовательность

30, 29, 28, ..., 3, 2, 1

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

Шаг 3. Вычисляем размер одного идентификатора

idx = ceil(23 * b / 8)

Идентификатор состоит из 23 символов.

Если каждый символ занимает b бит, то весь идентификатор займёт

23 * b бит.

Но память измеряется в байтах, поэтому делим на 8:

23 * b / 8

Получаем количество байт, которое требуется для хранения идентификатора.

Так как выделить можно только целое число байт, используем ceil().

Например, если b = 15:

23 * 15 = 345 бит

345 / 8 = 43.125 байта

ceil(43.125) = 44 байта

Значит, один идентификатор займёт 44 байта.

Шаг 4. Проверяем, хватает ли памяти

if 500_000 * idx <= 21 * 1024 * 1024:

idx — размер одного идентификатора в байтах.

Тогда

500_000 * idx

— это объём памяти, необходимый для хранения всех идентификаторов.

Правая часть

21 * 1024 * 1024

переводит 21 Мбайт в байты:

21 × 1024 × 1024 = 22 020 096 байт

Если требуемая память не превышает имеющуюся, условие выполняется.

Шаг 5. Выводим мощность алфавита

print(2 ** b)

Если один символ кодируется b битами, то можно закодировать

2^b

различных символов.

Например:

Бит на символ	Максимальная мощность алфавита
8	256
10	1024
12	4096
15	32768

Именно это число требует вывести задача.

Шаг 6. Завершаем работу программы

break

Так как перебор идёт от большего значения к меньшему, первое найденное подходящее значение b уже является максимальным.

После вывода ответа дальнейший перебор не нужен, поэтому команда break сразу завершает цикл.

Идея всего алгоритма

1. Предполагаем, что символ кодируется 30 битами.

2. Вычисляем размер одного идентификатора.

3. Проверяем, помещаются ли все идентификаторы в память.

4. Если нет — уменьшаем количество бит на символ на 1 и повторяем проверку.

5. Как только найдено первое подходящее значение, вычисляем 2^b — это и есть максимальная возможная мощность алфавита.