Все задачи №11
№11

минимальная мощность алфавита, объём «не менее»

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 3 845 627 серийных номеров требуется не менее 11 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Источник: ФИПИ (Демо), № 23749

Ответвпиши то, что получилось
Показать разбор
  1. Переведи память в байты: 11 · 1024³.
  2. Раздели на 3 845 627 и округли вверх: столько байт на номер нужно как минимум.
  3. Перебирай i: байт на номер = 2783 · i / 8, округли вверх.
  4. Найди наименьшее i, при котором байт хватает.
  5. Минимальная мощность при таком i равна 2^(i − 1) + 1.