Предприятие выпускает партии изделий. Каждая партия получает уникальный код, состоящий из 19 заглавных латинских букв. Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии. Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию. Код изделия состоит из кода партии и номера изделия в партии. Для записи кода партии используется посимвольное кодирование, каждый символ кодируется минимально возможным количеством битов. Номер изделия записывается как целое число, для записи каждого номера используется одинаковое минимальное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов. Для записи дополнительной информации о каждом изделии требуется 40 байт. Известно, что для хранения информации обо всех изделиях одной партии используется не более 20 Кбайт. Какое наибольшее количество изделий может быть в партии?

Question

Решение:

Код партии: $N_1 = 26$ $\Rightarrow$ $b_1 = 5$ бит. Длина: $L_1 = 19$ $\Rightarrow$ $19 \cdot 5 = 95$ бит.

Пусть $M$ — количество изделий в партии. Номер изделия: числа от $1$ до $M$ $\Rightarrow$ $b_2 = \lceil \log_2 M \rceil$ бит.

Объём кода изделия в битах: $95 + b_2$ . В байтах: $\lceil (95 + b_2) / 8 \rceil$ .

Дополнительная информация: $40$ байт. Всего на одно изделие: $\lceil (95 + b_2) / 8 \rceil + 40$ байт. На $M$ изделий: $M \cdot \left( \lceil (95 + b_2) / 8 \rceil + 40 \right) \le 20 \cdot 1024 = 20\,480$ .

Подбираем $M$ и $b_2 = \lceil \log_2 M \rceil$ . Перебираем $b_2$ :

$b_2=8$ : $\lceil (95+8)/8 \rceil = \lceil 103/8 \rceil = 13$ , сумма $13+40=53$ , $M \le 20480/53 \approx 386,4$ . При $b_2=8$ максимальное $M$ с таким $b_2$ — до $2^8=256$ , но $256 < 386$ , значит, можно взять $M=386$ ? При $M=386$ $b_2=9$ (так как $2^8=256<386$ ), тогда пересчёт: $b_2=9$ : $\lceil (95+9)/8 \rceil = \lceil 104/8 \rceil = 13$ , сумма $13+40=53$ , $M \le 386$ — подходит. При $M=386$ и $b_2=9$ условие выполняется: $386 \cdot 53 = 20\,458 < 20\,480$ . Проверим $M=387$ : $b_2=9$ та же, $387 \cdot 53 = 20\,511 > 20\,480$ — не подходит. Значит, максимум $M=386$ .

Ответ:

386

Accepted Answer

386