Помогите решить задачку из демо лицея по инфе (10 класс)

Question

На время ремонта участка Замоскворецкой линии метро Вася вынужден добираться до Лицея на автобусах. Он может доехать до остановки «метро Каширская» на следующих автобусах: КМ1, КМ2, Е80, 899, С820 и Н13. Известно, что интервалы движения автобусов  составляют: КМ1 – 120 сек., КМ2 – 120 сек., Е80 – 150 сек., 899 – 250 сек., С820 – 300 сек., Н13 – 375 сек.  Вася захотел зафиксировать последовательность прибытия автобусов на остановку, но забыл дома ручку. У него есть лист бумаги и стикеры (наклейки) двух цветов. В Лицее на уроках информатики Вася изучил неравномерное двоичное кодирование. Поэтому, для каждого номера автобуса Вася разработал двоичный код, удовлетворяющий условию Фано. Какое минимальное количество стикеров понадобится Васе, чтобы закодировать подъезжающие к остановке автобусы, если автобусов подъехало: КМ1 – 4шт., КМ2 – 3шт., Е80 – 3 шт., 899 – 2 шт., С820 – 2шт.   В ответе запишите общее количество стикеров

chromatic_scale · Accepted Answer

Чтобы определить минимальное количество стикеров, необходимое Васе для кодирования последовательности прибытия автобусов, нужно воспользоваться принципами оптимального двоичного кодирования (например, методом Хаффмана).
**Шаги решения:**
1. **Определение частот:**
   - КМ1: 4 прибытия
   - КМ2: 3 прибытия
   - Е80: 3 прибытия
   - 899: 2 прибытия
   - С820: 2 прибытия
2. **Построение дерева Хаффмана:**
   - Объединяем наименее частотные автобусы (С820 и 899) с частотой 2 каждая → узел с частотой 4.
   - Далее объединяем КМ2 и Е80 с частотой 3 каждая → узел с частотой 6.
   - Объединяем полученные узлы с КМ1 и узлом частоты 4 → итоговое дерево.
3. **Назначение кодов:**
   - КМ1: `11` (2 бита)
   - КМ2: `00` (2 бита)
   - Е80: `01` (2 бита)
   - С820: `100` (3 бита)
   - 899: `101` (3 бита)
4. **Вычисление общего количества бит:**
   - КМ1: 4 × 2 = 8 бит
   - КМ2: 3 × 2 = 6 бит
   - Е80: 3 × 2 = 6 бит
   - С820: 2 × 3 = 6 бит
   - 899: 2 × 3 = 6 бит
   **Итого:** 8 + 6 + 6 + 6 + 6 = **32 стикера**
Таким образом, минимальное количество стикеров, необходимых Васе для кодирования всех прибытия автобусов, составляет **32**.
**Ответ:** 32