Question

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

Accepted Answer

257

Answer

Идея решения: найти минимальное количество бит для кодирования одного символа, затем перебрать длины номеров в убывающем порядке, проверяя, укладывается ли требуемый объём памяти в ограничение. **Шаг 1. Определяем мощность алфавита.** Всего символов: $10 + 52 + 963 = 1025$. **Шаг 2. Находим минимальное количество бит на символ.** Нужно найти минимальное $k$ такое, что $2^k \ge 1025$. $2^{10} = 1024 < 1025$, $2^{11} = 2048 \ge 1025$. Следовательно, $k = 11$ бит на один символ. **Шаг 3. Вычисляем объём памяти для номера длины $x$.** Один номер длины $x$ занимает $11x$ бит. После округления до целого числа байт: $$ ext{байт на номер} = \left\lceil \frac{11x}{8} ight ceil$$ **Шаг 4. Проверяем ограничение на 2000 номеров.** Общий объём: $2000 \cdot \left\lceil \frac{11x}{8} ight ceil \le 693 \cdot 1024$ байт. Упрощаем: $$\left\lceil \frac{11x}{8} ight ceil \le \frac{693 \cdot 1024}{2000} = 354{,}816$$ Следовательно, $\left\lceil \frac{11x}{8} ight ceil \le 354$. **Шаг 5. Находим максимальное $x$.** Из условия $\left\lceil \frac{11x}{8} ight ceil \le 354$ получаем: $$\frac{11x}{8} \le 354 \implies 11x \le 2832 \implies x \le 257{,}45.$$ Максимальное целое значение: $x = 257$. - При $x = 257$: $11 \cdot 257 = 2827$ бит, $\left\lceil \frac{2827}{8} ight ceil = 354$ байта. - Для 2000 номеров: $354 \cdot 2000 = 708000$ байт $= 691{,}4$ Кбайт $\le 693$ Кбайт. ✓ - При $x = 258$: $11 \cdot 258 = 2838$ бит, $\left\lceil \frac{2838}{8} ight ceil = 355$ байт. - Для 2000 номеров: $355 \cdot 2000 = 710000$ байт $= 692{,}4$ Кбайт $\le 693$ Кбайт. ✓ - При $x = 259$: $11 \cdot 259 = 2849$ бит, $\left\lceil \frac{2849}{8} ight ceil = 357$ байт. - Для 2000 номеров: $357 \cdot 2000 = 714000$ байт $= 696{,}9$ Кбайт $> 693$ Кбайт. ✗ Проверим $x = 258$ точнее: $\frac{2838}{8} = 354{,}75$, округляем вверх до 355 байт. $355 \cdot 2000 = 710000$ байт. $\frac{710000}{1024} \approx 692{,}38$ Кбайт $\le 693$ Кбайт. Проверим $x = 259$: $\frac{2849}{8} = 356{,}125$, округляем вверх до 357 байт. $357 \cdot 2000 = 714000$ байт. $\frac{714000}{1024} \approx 696{,}88$ Кбайт $> 693$ Кбайт. Максимальная длина — 257. ```python m = 10 + 52 + 963 k = 1 while 2**k < m: k += 1 for x in range(10000, 1, -1): bits = x * k bytes_per_num = bits // 8 if bits % 8 != 0: bytes_per_num += 1 if bytes_per_num * 2000 <= 693 * 1024: print(x) break ``` ![Рисунок](https://ege.sdamgia.ru/formula/svg/73/73ff7f598ce3b3ca3f7db61d8d2785cf.svg) ![Рисунок](https://ege.sdamgia.ru/formula/svg/65/65c84ff0702e454d8201201e16cfec62.svg) ![Рисунок](https://ege.sdamgia.ru/formula/svg/1c/1c76bbd275fe46bf072a0e8bd47168d0.svg) ![Рисунок](https://ege.sdamgia.ru/formula/svg/7e/7ec3759bbd5e26b88d152438044f0758.svg) ![Рисунок](https://ege.sdamgia.ru/formula/svg/a0/a05076f501f49d04cd19795a3af9ea0b.svg)

Задание №11Представление информацииЕГЭ по информатике