7 Решение на Python — перебор (задачи последних лет)
Решение на Python — перебор (задачи последних лет)
В последние годы в задании 11 часто встречаются обратные задачи с неравенством: дан общий объём (с «превысил», «не менее», «не более»), и нужно найти минимальную мощность алфавита или минимальную длину записи. Руками такое считать муторно — легко ошибиться с округлением и направлением неравенства. Гораздо надёжнее перебор: пробуем неизвестное от 1 вверх, считаем объём и печатаем первое значение, при котором условие выполнено.
Пример: найти минимальную мощность алфавита
Условие Каждая запись — строка из 377 символов алфавита мощностью |
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` на степенях двойки
|