Определение длины серийного номера: На предприятии каждой; 49, 52, 500, 45 · ЕГЭ №11

Условие, ответ и разбор задачи

Вычисление количества информации

На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 500-символьного специального алфавита. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 45 877 серийных номеров требуется более 49 Мбайт памяти. Определите минимально допустимую длину серийного номера. В ответе запишите только целое число.

Ответ:

Решение

Алфавит: 10 цифр + 52 буквы + 500 специальных символов = 562 символа, 10 бит на символ (2^10 = 1024).

Памяти требуется больше 49 Мбайт, значит на один номер больше 49 × 1024 × 1024 / 45877 = 1119,96 байт, то есть не меньше 1120 байт.

Номер длины L занимает 10L бит, то есть 1,25L байт с округлением вверх.

При L = 895: 1118,75 → 1119 байт, этого мало. При L = 896: ровно 1120 байт — подходит.

Минимально допустимая длина — 896.

Тот же ответ даёт перебор по длине:

from math import ceil
for L in range(1, 10000):
    if 45877 * ceil(L * 10 / 8) > 49 * 1024 * 1024:
        print(L)
        break

$\textbf{Ответ: 896.}$

Определение длины серийного номера: На предприятии каждой; 49, 52, 500, 45 · ЕГЭ №11

Похожие задачи