ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Открытое личное первенство УрГУ 2011

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Таблицы маршрутизации

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Чтобы управлять движением сетевых пакетов, используются специальные устройства — маршрутизаторы. Поведение маршрутизатора определяется таблицей маршрутизации. Эта таблица состоит из нескольких строк, каждая из которых содержит IP-адрес сети назначения d, маску m и IP-адрес шлюза g. Например, строка «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-битное число. Для удобства он разбивается на четыре байта, каждый из них записывается в десятичном виде, а между байтами ставятся точки. Так, IP-адрес 11000000101010000001100000000000 записывается как 192.168.24.0. Маски имеют такой же вид, при этом в двоичном представлении маски сначала идут только единицы, а потом — только нули.
Когда на маршрутизатор приходит пакет, отправленный на адрес 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


Напишите программу для сравнения двух таблиц маршрутизации.

Исходные данные

В первой строке записано целое число — количество строк в первой таблице маршрутизации. Далее идёт эта таблица в описанном выше формате. Затем аналогичным образом описывается вторая таблица маршрутизации. Общее количество строк в таблицах не превосходит 65536.

Результат

Если таблицы эквивалентны, выведите «YES», в противном случае выведите «NO».

Примеры

исходные данныерезультат
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
YES

1
192.168.0.0 255.255.255.0 192.168.14.1
2
192.168.0.0 255.255.255.0 192.168.14.1
172.16.0.0 255.255.0.0 172.16.0.1
NO
Автор задачи: Игорь Андрианов
Источник задачи: XII открытое личное первенство УрГУ (19 марта 2011)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1829. Таблицы маршрутизации