Объём сообщения

Когда использовать: Известны все символы алфавита и количество символов в сообщении; нужно найти объём в битах или байтах.

1. Перечислите все различные символы и найдите N.
2. Найдите минимальное i: наименьшее целое, при котором 2^i ≥ N.
3. Умножьте длину сообщения на i — получите биты.
4. Разделите на 8 и округлите вверх, если нужны целые байты.
5. Проверьте, что в алфавит включены цифры, регистр и специальные знаки.

from math import ceil, log2

N = 33 * 2 + 10 + 50 * 5
i = ceil(log2(N))
K = 1016
print(N, i, K * i // 8)

По мотивам задачи № 19360 (база Kompege).

Когда использовать: Дан идентификатор фиксированной длины, алфавит и количество записей; нужно найти общий объём.

1. Найдите мощность алфавита N.
2. Посчитайте i = ceil(log2 N).
3. Умножьте длину идентификатора на i — получите биты.
4. Переведите в байты с округлением вверх: это размер одной записи.
5. Умножьте на количество записей и переведите в Кбайт или Мбайт.

from math import ceil, log2

N = 1337 + 10
i = ceil(log2(N))
size = ceil(127 * i / 8)
print(i, size, 16384 * size // 1024)

По мотивам задачи № 9951 (база Kompege).

Когда использовать: Запись состоит из нескольких частей с разными алфавитами; нужно найти общий объём.

1. Для каждого поля отдельно найдите N и i.
2. Посчитайте биты каждого поля.
3. Если поля округляются по отдельности, переведите каждое в байты вверх.
4. Сложите размеры полей — получите размер записи.
5. Умножьте на количество записей и переведите в нужные единицы.

from math import ceil, log2

def field_bytes(length, N):
    return ceil(length * ceil(log2(N)) / 8)

login = field_bytes(5, 16)
password = field_bytes(11, 26 + 26 + 10 + 8)
print(login, password, 262144 * (login + password) // 1024)

По мотивам задачи № 11911 (база Kompege).

Когда использовать: Поле принимает значения из диапазона, например год от 1 до 2100 или день от 1 до 31.

1. Для каждого поля определите количество возможных значений M.
2. Найдите i = ceil(log2 M): это минимальное число бит для поля.
3. Сложите биты всех полей.
4. Если спрашивают минимальное число байт для записи, округлите сумму вверх.
5. Не путайте последнее значение диапазона с количеством значений.

from math import ceil, log2

bits = ceil(log2(2100)) + ceil(log2(12)) + ceil(log2(31))
print(bits)

По мотивам задачи № 719 (база Kompege).

Когда использовать: Даны общий объём и связь между длинами двух полей, например логин на 21 символ длиннее пароля.

1. Найдите объём, приходящийся на одну запись.
2. Вычтите известные поля и дополнительные сведения.
3. Выразите неизвестную длину через x.
4. Составьте уравнение по битам или байтам.
5. Решите уравнение и проверьте, что длина целая.

for x in range(1, 100):
    if 4 * x + 11 * (x + 21) == 72 * 8:
        print(x, x + 21)

По мотивам задачи № 11704 (база Kompege).

Когда использовать: Известны общий объём, количество пользователей и размер пароля; нужно найти доп. сведения.

1. Найдите размер одной записи: общий объём разделите на количество.
2. Посчитайте размер пароля или кода в байтах.
3. Вычтите его из размера записи.
4. Проверьте, что результат целый и не отрицательный.
5. Подставьте найденное значение обратно в общий объём.

from math import ceil, log2

i = ceil(log2(10 + 26 + 26 + 5))
password = ceil(9 * i / 8)
per_user = 500 // 20
print(i, password, per_user - password)

По мотивам задачи № 26053 (база Kompege).

Когда использовать: Известны длина, количество записей и граница объёма; нужно найти мощность алфавита.

1. Свяжите размер записи с i: S = ceil(L · i / 8).
2. Запишите неравенство для общего объёма.
3. Перебирайте i от 1 вверх или от большого значения вниз.
4. Для найденного i возьмите минимальное N = 2^(i−1) + 1 или максимальное N = 2^i.
5. Проверьте соседнее i: оно должно уже нарушать границу.

from math import ceil, log2

for i in range(1, 20):
    size = ceil(206 * i / 8)
    if 601058 * size >= 143 * 1024 * 1024:
        print(i, 2 ** (i - 1) + 1)
        break

По мотивам задачи № 23504 (база Kompege).

Когда использовать: Известны мощность алфавита, количество записей и граница объёма; нужно найти длину.

1. Найдите вес символа i по мощности алфавита.
2. Выразите размер записи через длину L: ceil(L · i / 8).
3. Запишите неравенство для общего объёма.
4. Перебирайте L в нужную сторону до первого подходящего значения.
5. Проверьте, что следующая длина уже нарушает условие.

from math import ceil, log2

i = ceil(log2(10 + 58 + 1982))
for L in range(1000, 0, -1):
    if 2144 * ceil(L * i / 8) <= 986.3 * 1024:
        print(L, i)
        break

По мотивам задачи № 23023 (база Kompege).

Когда использовать: Нужно закодировать M уникальных объектов, а затем посчитать объём получившихся номеров.

1. Найдите N и i.
2. Подберите минимальную длину L, при которой N^L ≥ M.
3. Посчитайте размер одного номера: ceil(L · i / 8).
4. Умножьте на количество номеров.
5. Переведите в требуемые единицы и при необходимости возьмите целую часть.

from math import ceil, log2

N = 10 + 62
i = ceil(log2(N))
count = 10_000_000
L = 1
while N ** L < count:
    L += 1
size = ceil(L * i / 8)
print(L, size, int(count * size / 1024 / 1024))

По мотивам задачи № 26085 (база Kompege).

Когда использовать: Есть несколько групп записей разной длины, но алфавит у них один и тот же.

1. Обозначьте мощность алфавита N и выразите i = ceil(log2 N).
2. Для каждой длины посчитайте размер записи в байтах.
3. Умножьте размеры на количество записей каждого типа.
4. Сложите и приравняйте к общему объёму.
5. Перебирайте N; проверьте минимальное и максимальное подходящее значение.

from math import ceil, log2

for N in range(2, 10000):
    i = ceil(log2(N))
    a = ceil(7 * i / 8)
    b = ceil(9 * i / 8)
    if 384 * a + 256 * b == 7168:
        print(N, i)
        break

По мотивам задачи № 29070 (база Kompege).

Когда использовать: Сказано «более 51 Мбайт и менее 52 Мбайт» или «не более 955 Кбайт»; нужно найти все подходящие мощности.

1. Переведите границы в байты.
2. Разделите на количество записей и получите допустимый размер одной записи.
3. Для «не более» берите целую часть вниз, для «не менее» — вверх; строгие границы не включайте.
4. Для каждого допустимого размера найдите i и проверьте, что ceil(L · i / 8) даёт этот размер.
5. Для найденного i посчитайте количество N: от 2^(i−1) + 1 до 2^i.

from math import ceil

low = 51 * 1024 * 1024
high = 52 * 1024 * 1024
lo = ceil(low / 125700)
hi = int(high / 125700)
variants = 0
for i in range(1, 40):
    size = ceil(312 * i / 8)
    if lo <= size <= hi:
        variants += 2 ** i - 2 ** (i - 1)
print(variants)

По мотивам задачи № 18978 (база Kompege).

Когда использовать: Нужно сравнить два способа кодирования: исходный алфавит и алфавит после замены одного символа на последовательность.

1. Посчитайте объём первым способом: K1 · i1.
2. При замене пересчитайте длину: каждый заменённый символ даёт два новых.
3. Пересчитайте мощность алфавита: старый символ исчезает, новые уже могли входить в алфавит.
4. Посчитайте объём вторым способом.
5. Сравните объёмы и запишите букву способа и разницу.

first = 1000 * 6
second = (1000 - 15 + 30) * 5
print(first, second, first - second)

По мотивам задачи № 17697 (база Kompege).

Когда использовать: Ответ уже получен, но нужно быстро найти обидную ошибку.

• Подставьте найденный размер записи обратно в общий объём.
• Проверьте, что при следующем i или L объём выходит за указанную границу.
• Убедитесь, что ответ в тех единицах, которые просят: биты, байты, Кбайт или Мбайт.
• Проверьте, что 1 Кбайт считался как 1024 байта.
• Пересчитайте алфавит: цифры, оба регистра, пробелы и специальные знаки.
• Убедитесь, что поля с разными алфавитами считались отдельно.
• Не округляйте вниз, если запись должна занимать минимальное целое число байт.
• Если ответ — мощность алфавита, проверьте, что N целое и больше 1.
• Если ответ содержит букву, сначала определите более выгодный способ, затем разницу.
• Проверьте, что не перепутаны длина номера и мощность алфавита.
• Для строгих границ «более» и «менее» не включайте граничное значение.
• Сделайте обратный счёт: количество · размер записи ≤ или ≥ заданного объёма.