7 Решение на Python — перебор (задачи последних лет)

Решение на Python — перебор (задачи последних лет)

В последние годы в задании 11 часто встречаются обратные задачи с неравенством: дан общий объём (с «превысил», «не менее», «не более»), и нужно найти минимальную мощность алфавита или минимальную длину записи. Руками такое считать муторно — легко ошибиться с округлением и направлением неравенства. Гораздо надёжнее перебор: пробуем неизвестное от 1 вверх, считаем объём и печатаем первое значение, при котором условие выполнено.

Пример: найти минимальную мощность алфавита

Условие

Каждая запись — строка из 377 символов алфавита мощностью n (все символы кодируются минимальным и одинаковым числом бит). Всего хранится 23 155 записей. Известно, что суммарный объём превысил 5536 Кбайт. Найдите минимальную мощность алфавита n.

from math import *

for n in range(1, 100000):          # перебираем мощность алфавита n
    i = ceil(log2(n))               # бит на символ: наименьшее i с 2^i >= n
    k = 377                         # длина записи (из условия)
    V = ceil(i * k / 8)             # байт на одну запись (округляем вверх)
    if 23155 * V > 5536 * 1024:     # суммарный объём превысил 5536 Кбайт?
        print(n)                    # первое подходящее n — это минимум
        break

Программа печатает 33. Проверим смысл: при n = 33 нужно i = 6 бит (2⁵ = 32 < 33 ≤ 64 = 2⁶), на запись уходит ⌈6·377/8⌉ = 283 байта, а всего 23155 · 283 = 6 552 865 байт — это больше 5536 · 1024 = 5 668 864. При n = 32 хватило бы 5 бит и объём вышел бы меньше порога, поэтому 33 — минимальная мощность.

Ответ: 33

Как устроен перебор

  • Перебираем неизвестное. for n in range(1, 100000) — пробуем мощность алфавита по возрастанию. Если ищут длину записи — перебираем длину; если мощность — перебираем её.

  • Считаем объём по цепочке. Бит на символ i = ceil(log2(n)), байт на запись V = ceil(i*k/8) (обязательно вверх — отсюда ceil), суммарно число_записей · V.

  • Условие — из текста задачи. «Превысил / больше / не менее» — это > или >=; «меньше / не более / поместилось» — < или <=. Ставь ровно тот знак, что в условии.

  • `break` на первом попадании. Раз перебор идёт по возрастанию, первое подходящее n и есть минимум. Если бы просили максимальную длину/мощность, при которой объём ещё не превышает предел, — убирали бы break и запоминали последнее подходящее значение (либо шли перебором сверху вниз).

📌 Надёжнее, чем `log2` на степенях двойки

ceil(log2(n)) изредка «спотыкается» на точных степенях двойки из-за погрешности вещественных чисел. Абсолютно надёжная замена — (n - 1).bit_length(): она тоже даёт наименьшее i с 2ⁱ ≥ n, но без дробных чисел. В строке с i можно смело писать i = (n - 1).bit_length().

Решение на Python — перебор (задачи последних лет) — Задание 11 ЕГЭ 20 | Методички — Профиматика