Сжатие списка подсетей IPv4
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Разбор и проверка данных
- Математика
- Массивы и списки
Подсеть IPv4 записывается как A.B.C.D/P: адрес из четырёх чисел от 0 до 255 и длина префикса P от 0 до 32. Подсеть содержит все адреса (32-битные числа), у которых совпадают первые P битов с данным адресом. Подсеть нормализована, если все биты адреса после префикса равны нулю: 10.8.1.2/24 задаёт ту же подсеть, что и 10.8.1.0/24, а нормализация 255.255.255.255/13 — 255.248.0.0/13.
Дан список подсетей (возможны повторы и пересечения). Верните самый короткий список нормализованных подсетей, который покрывает ровно те же адреса, что и входной. Такой список единственный; упорядочьте его по возрастанию адреса (по числовому значению, то есть сначала по первому числу, затем по второму и так далее).
Ограничения: до 10000 подсетей. Подсети длины 0 записываются как 0.0.0.0/0.
Пример: ["10.1.2.3/8", "10.2.3.4/17"] → ["10.0.0.0/8"] (вторая подсеть целиком лежит в первой).
Источник: Coding Competitions Archive, kickstart/2015/round_d/ip_address_summarization · © Google LLC · Apache-2.0 · условие переведено и дополнено