АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
Textbooks FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

910. Rоuting

Time Limit: 1 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added 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

 


View Problem Statistics Submit Problem discussion Author/source:
Problems from Contests / Vologda Students Contests / XIV InterUni Olympiad 2011 /
909. H - Cellular communications 910. 911. J - Weighting-2 912. X - Weighting
time generating 0.094 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.