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

Номер изделия в партии

Ответ прячется в условии

Партия изделий. У партии свой код, у каждого изделия — номер от 1 до общего количества изделий.

И вот засада: сколько бит уходит на номер, зависит от того самого количества, которое и надо найти.

Прикинь, потом подтверди

Круг разрывается прикидкой. Предположи число бит на номер — скажем, 9. Собери запись, раздели на неё память, посмотри, сколько изделий вышло.

Вышедшее количество укладывается в 9 бит — прикидка верна. Не укладывается — бери соседнее число бит и считай заново.

Прикинь, потом подтверди. Ответ обязан быть согласован сам с собой.

Пример: партия из 25 букв

Код партии — 25 заглавных латинских букв по 5 бит, всего 125 бит. Дополнительные сведения — 60 байт на изделие. Памяти 30 Кбайт, то есть 30 720 байт.

Пробуем 9 бит на номер. Код целиком: 125 + 9 = 134 бита, это 17 байт. Запись: 17 + 60 = 77 байт.

30 720 : 77 = 398 с остатком. Проверяем согласованность: для 398 номеров девяти бит хватает (2⁸ = 256 мало, 2⁹ = 512 достаточно). Сходится.

Сосед не проходит: 399 · 77 = 30 723 байта, а памяти всего 30 720.

import math

code = 25 * math.ceil(math.log2(26))   # бит на код партии: 25 заглавных букв
extra = 60                             # байт на дополнительные сведения
limit = 30 * 1024                      # всего байт памяти

answer = 0
for n in range(1, 1000):               # пробуем каждое количество изделий
    b = math.ceil(math.log2(n))        # бит на номер изделия
    record = math.ceil((code + b) / 8) + extra
    if n * record <= limit:
        answer = n                     # столько изделий ещё помещается

b = math.ceil(math.log2(answer))
record = math.ceil((code + b) / 8) + extra

print(code)
print(b)
print(record)
print(answer)
print(answer * record)
print((answer + 1) * record)

Программа печатает биты кода партии, биты номера, размер записи, ответ, объём при нём и объём при следующем количестве:

Проверь себя

Код партии — 15 заглавных латинских букв, каждая кодируется минимально возможным числом бит. Изделия нумеруются от 1 до общего их числа, на номер отводится одинаковое минимально возможное число бит. Код партии и номер вместе занимают целое число байт, дополнительные сведения — ещё 10 байт на изделие. На всю партию отведено 20 Кбайт. Какое наибольшее количество изделий может быть в партии?

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

Ловушки

Посчитали биты номера по прикидке и не проверили, что ответ в них укладывается.
Округлили до байта код партии, а потом ещё раз — номер.
Прибавили дополнительные сведения до округления кода.
Взяли количество изделий на единицу больше, чем помещается.

Печать