№11

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

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

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

from math import ceil, log2

for A in range(2, 1000000):
    bits = 20 * ceil(log2(A))
    bytes = ceil(bits / 8)
    if 600_000 * bytes > 11 * 2 ** 20:
        print(A)
        break

Рассмотрим программу по шагам.

Шаг 1. Импортируем функции

from math import ceil, log2

  • log2(x) вычисляет логарифм числа по основанию 2.

  • ceil(x) округляет число вверх до ближайшего целого.

Например:

log2(129) ≈ 7.01
ceil(7.01) = 8

Это означает, что для хранения одного символа потребуется 8 бит.

Шаг 2. Перебираем возможные мощности алфавита

for A in range(2, 1000000):

Переменная A обозначает мощность алфавита.

Программа последовательно проверяет все возможные значения:

2, 3, 4, 5, ..., 128, 129, ...

Наша задача — найти самое маленькое подходящее значение. Поэтому перебор начинается с 2 и идет по возрастанию.

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

bits = 20 * ceil(log2(A))

Каждый идентификатор состоит из 20 символов.

Сначала вычисляется, сколько бит необходимо для хранения одного символа:

ceil(log2(A))

Например:

  • алфавит из 50 символов → 6 бит;

  • алфавит из 100 символов → 7 бит;

  • алфавит из 129 символов → 8 бит.

Затем это число умножается на 20, так как символов в идентификаторе двадцать.

Например, если на один символ требуется 7 бит:

20 × 7 = 140 бит

Шаг 4. Переводим биты в байты

bytes = ceil(bits / 8)

Память выделяется только целыми байтами.

Если получилось:

140 бит

то делим на 8:

140 / 8 = 17.5 байта

Половину байта выделить нельзя, поэтому используем округление вверх:

ceil(17.5) = 18 байт

Именно столько памяти будет занимать один идентификатор.

Шаг 5. Проверяем условие задачи

if 600_000 * bytes > 11 * 2 ** 20:

Здесь вычисляется общий объем памяти для всех идентификаторов.

  • 600_000 * bytes — сколько байт займут 600 000 идентификаторов.

  • 11 2 * 20 — перевод 11 Мбайт в байты.

Сравниваем эти два значения.

Если памяти требуется больше, чем 11 Мбайт, значит условие задачи выполнено.

Шаг 6. Выводим ответ и заканчиваем программу

print(A)
break

Так как значения A перебираются по возрастанию, первое найденное значение уже является минимальным.

Команда break сразу завершает цикл, потому что дальше искать уже не нужно.

Итог

Программа последовательно проверяет все возможные мощности алфавита. Для каждой мощности она:

  1. вычисляет количество бит на один символ;

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

  3. вычисляет объем памяти для всех идентификаторов;

  4. проверяет условие задачи.

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

← К списку шпаргалок