Статья Автор: Деникина Н.В., Деникин А.В.

Обратный ход: длина кода

Известен объём, спрашивают длину

Те же шаги, только идём по ним снизу вверх: от памяти к символам.

Арифметика тут проще прямой задачи. Балл теряют не на ней, а на двух словах условия — «не более» и «более».

Дорога назад

Делим объём на количество кодов — получаем байты на один код. Дробную часть отбрасываем: байт целый.

Умножаем на 8, делим на биты одного символа — вот длина.

Наибольшее — вниз, наименьшее — вверх. «Отведено не более» просит максимум, «потребовалось более» — минимум.

Проверь соседа. Нашёл максимум — убедись, что следующая длина уже не помещается. Две строки арифметики, спасённый балл.

Пример: серийный номер

Демоверсия 2025 года. Номер содержит десятичные цифры, 52 латинские буквы с учётом регистра и символы из 963-символьного специального алфавита. Для 2000 номеров отведено не более 693 Кбайт. Какова наибольшая длина номера?

Алфавит целиком: 10 + 52 + 963 = 1025 символов. Тысячи двадцати четырёх мало, значит 11 бит на символ.

693 Кбайт — это 709 632 байта. На один номер приходится не больше 354 байт: 709 632 : 2000 = 354 с остатком.

354 байта — это 2832 бита, делим на 11 и получаем 257 символов.

import math

alpha = 10 + 52 + 963             # цифры, латиница с регистром, спецалфавит
count = 2000                      # серийных номеров
limit = 693 * 1024                # всего байт памяти

i = math.ceil(math.log2(alpha))   # бит на символ
per = limit // count              # байт на один номер, только целая часть
bits = per * 8                    # бит на один номер
length = bits // i                # символов в номере

print(alpha)
print(i)
print(per)
print(length)

Программа печатает:

Проверка соседа

Наращиваем длину по одному символу, пока база помещается в 693 Кбайт. Третья и четвёртая строки вывода — объём при 257 и при 258 символах.

import math

alpha = 10 + 52 + 963
count = 2000
limit = 693 * 1024
i = math.ceil(math.log2(alpha))

length = 0
while count * math.ceil((length + 1) * i / 8) <= limit:
    length = length + 1           # ещё один символ помещается

print(length)
print(count * math.ceil(length * i / 8))
print(count * math.ceil((length + 1) * i / 8))
print(limit)

Программа печатает длину, объём при ней, объём при длине на единицу больше и сам лимит:

Проверь себя

На один код отведено не более 100 байт, на символ уходит 7 бит. Какова наибольшая длина кода?

Проверить ответ

Ловушки

Оставили дробное число байт на код.
«Потребовалось более» посчитали как «не более» и промахнулись на единицу.
Не проверили соседнюю длину.
Килобайты умножили на 1000.

Печать