АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

910. Мaршрутизация

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Чтобы управлять движением сетевых пакетов, используются специальные устройства — маршрутизаторы. Поведение маршрутизатора определяется таблицей маршрутизации. Эта таблица состоит из нескольких строк, каждая из которых содержит 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 — операция побитового «и»). Затем он выбирает из них строку, количество единичных битов в маске которой максимально, и отправляет пакет на записанный в этой строке шлюз. Гарантируется, что для любого адреса назначения таких строк всегда будет не более одной.

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

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

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

В первой строке выходного файла выведите слово 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

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XIV Межвузовская олимпиада 2011 /
909. H - Сотовая связь 910. 911. J - Взвешивание-2 912. X - Взвешивание
 
время генерации 0.156 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.