Предприятие выпускает партии изделий. Каждая партия получает уникальный код, состоящий из 22 заглавных латинских букв. Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии.

Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию.

Код изделия состоит из кода партии и номера изделия в партии. Для записи кода партии используется посимвольное кодирование, каждый символ кодируется минимально возможным количеством битов. Номер изделия записывается как целое число, для записи каждого номера используется одинаковое минимальное возможное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов.

Для записи дополнительной информации о каждом изделии требуется 50 байт.

Известно, что для хранения информации обо всех изделиях одной партии используется не более 30 Кбайт. Какое наибольшее количество изделий может быть в партии?

Question

Предприятие выпускает партии изделий. Каждая партия получает уникальный код, состоящий из 22 заглавных латинских букв. Все изделия в партии получают последовательные номера от 1 до общего числа изделий в партии.

Запись о каждом изделии заносится в информационную систему. Запись содержит код изделия и некоторую дополнительную информацию.

Код изделия состоит из кода партии и номера изделия в партии. Для записи кода партии используется посимвольное кодирование, каждый символ кодируется минимально возможным количеством битов. Номер изделия записывается как целое число, для записи каждого номера используется одинаковое минимальное возможное количество битов. Для записи кода изделия в целом используется минимально возможное целое количество байтов.

Для записи дополнительной информации о каждом изделии требуется 50 байт.

Известно, что для хранения информации обо всех изделиях одной партии используется не более 30 Кбайт. Какое наибольшее количество изделий может быть в партии?

Решение:

Код партии: мощность алфавита $N_1 = 26$ (заглавные латинские буквы).
Глубина кодирования: $2^4 = 16 < 26$ , $2^5 = 32 \ge 26$ $\Rightarrow$ $b_1 = 5$ бит.
Длина кода партии: $L_1 = 22$ символа.
Объём кода партии в битах: $22 \cdot 5 = 110$ бит.
Пусть $M$ — количество изделий в партии.
Номер изделия: числа от $1$ до $M$ .
Глубина кодирования номера: $b_2 = \lceil \log_2 M \rceil$ бит.
Объём кода изделия (код партии + номер) в битах: $110 + b_2$ бит.
В байтах: $\left\lceil \dfrac{110 + b_2}{8} \right\rceil$ .
Дополнительная информация: $50$ байт на изделие.
Объём записи об одном изделии: $\left\lceil \dfrac{110 + b_2}{8} \right\rceil + 50$ байт.
Для $M$ изделий: $M \cdot \left( \left\lceil \dfrac{110 + b_2}{8} \right\rceil + 50 \right) \le 30 \cdot 1024 = 30\,720$ байт.
Подбираем $M$ и $b_2 = \lceil \log_2 M \rceil$ .
Рассмотрим возможные $b_2$ :

$b_2 = 8$ : $\left\lceil \dfrac{110+8}{8} \right\rceil = \left\lceil \dfrac{118}{8} \right\rceil = \lceil 14,75 \rceil = 15$ .
Сумма $15 + 50 = 65$ .
Тогда $M \le \dfrac{30\,720}{65} \approx 472,6$ .
При $b_2=8$ максимальное $M$ не превышает $2^8 = 256$ , но $256 < 472$ , значит, при $b_2=8$ можно взять $M=256$ .
Однако при $M=256$ $b_2=8$ , объём: $256 \cdot 65 = 16\,640 < 30\,720$ .
$b_2 = 9$ : $\left\lceil \dfrac{110+9}{8} \right\rceil = \left\lceil \dfrac{119}{8} \right\rceil = \lceil 14,875 \rceil = 15$ .
Сумма $15 + 50 = 65$ .
$M \le \dfrac{30\,720}{65} \approx 472,6$ .
При $b_2=9$ максимальное $M$ может быть до $2^9 = 512$ , но ограничение $M \le 472$ .
Берём $M = 472$ , проверяем: $b_2 = \lceil \log_2 472 \rceil = 9$ (так как $2^8=256<472$ , $2^9=512$ ), подходит.
Объём: $472 \cdot 65 = 30\,680 < 30\,720$ .
$b_2 = 10$ : $\left\lceil \dfrac{110+10}{8} \right\rceil = \left\lceil \dfrac{120}{8} \right\rceil = 15$ .
Сумма $15 + 50 = 65$ , но при $b_2=10$ $M \ge 513$ , тогда $65 \cdot 513 = 33\,345 > 30\,720$ — не подходит.

Наибольшее $M$ , удовлетворяющее условию: $M = 472$ .

Ответ:

472

Accepted Answer

472