eolymp
bolt
Try our new interface for solving problems
Məsələlər

Маршрутизация

Маршрутизация

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Для определения маршрутов движения сетевых пакетов в современных сетях используются специальные устройства — маршрутизаторы. В своих действиях маршрутизатор руководствуется таблицей маршрутизации. Такая таблица представляет набор строк, описывающих маршруты. Каждая строка содержит 3 поля — D, M и G, где D — IP-адрес сети назначения, M — маска, G — IP-адрес шлюза (заметим для точности, что в реальных таблицах полей больше). Например, строка 192.168.24.0 255.255.255.0 192.168.14.1 означает, что пакет, адресованный в сеть 192.168.24.0 с маской 255.255.255.0, нужно отправлять через шлюз 192.168.14.1.

Краткая справка. IP-адрес представляет собой 32-битное число. Для удобства он записывается в десятично-точечном формате, то есть каждый байт представляется в десятичном виде, а между ними ставятся точки. Например, запись 192.168.24.0 означает двоичное число 11000000101010000001100000000000. Это же верно и для масок. У масок есть важная особенность: в двоичном представлении маски всегда вначале идут только единицы, а потом — только нули. Адрес шлюза не может состоять целиком из нулевых или единичных битов.

Алгоритм выбора маршрута выглядит так. Пусть имеется пакет, адресованный на адрес A. Вначале маршрутизатор просматривает все записи и оставляет только те, где выполняется условие D and M = A and M (and — операция побитового "И"). Затем уже из этих записей оставляется та, где количество единичных битов в маске максимально — она и будет результатом. Гарантируется, что для любого адреса таких записей всегда будет не более одной.

Чем больше размер таблицы, тем медленнее маршрутизатор работает и больше ресурсов потребляет. Но во многих случаях исходную таблицу можно преобразовать в эквивалентную ей, но содержащую меньше строк.

Например, пусть первая таблица выглядит так:

192.168.0.0 255.255.255.0 192.168.14.1

192.168.1.0 255.255.255.0 192.168.14.1

192.168.2.0 255.255.255.0 192.168.14.2

192.168.3.0 255.255.255.0 192.168.14.2

Вторая таблица выглядит так:

192.168.0.0 255.255.252.0 192.168.14.1

192.168.2.0 255.255.254.0 192.168.14.2

Нетрудно убедиться, что для любого адреса назначения по этим двум таблицам определится один и тот же шлюз (либо никакой не определится). Заметим, что в данной задаче адресом назначения может быть любое 32-битное число (то есть нет специальных и недопустимых адресов, как в реальных сетях).

Таблицы большого размера сравнивать вручную весьма трудоёмко. От вас требуется написать программу для проверки эквивалентности двух заданных таблиц.

Giriş verilənləri

В первой строке входного файла записано целое число N (от 1 до 100 000) — количество записей в первой таблице маршрутизации. Следующие N строк содержат таблицу маршрутизации в описанном выше формате. Затем записано целое число M (от 1 до 100 000) — количество записей во второй таблице. Следующие M строк содержат вторую таблицу маршрутизации.

Çıxış verilənləri

В первой строке выходного файла выведите слово YES или NO.

Nümunə

Giriş verilənləri #1
4
192.168.0.0 255.255.255.0 192.168.14.1
192.168.1.0 255.255.255.0 192.168.14.1
192.168.2.0 255.255.255.0 192.168.14.2
192.168.3.0 255.255.255.0 192.168.14.2
2
192.168.0.0 255.255.252.0 192.168.14.1
192.168.2.0 255.255.254.0 192.168.14.2
Çıxış verilənləri #1
YES