Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Маска подсетей

(Время: 1 сек. Память: 16 Мб Сложность: 33%)

Рассмотрим компьютерную сеть с настроенной TCP/IP маршрутизацией. Будем рассматривать некоторую ее модификацию. А именно в этой сети находить N подсетей. Каждая подсеть характеризуется своей маской. Маска подсети представляет собой 4 однобайтных числа, разделенных точкой. Причем для масок выполнено следующее свойство: если представить маску в двоичном виде, то сначала она будет содержать k единиц, а потом q нулей, причем k + q = 32. Например, 255.255.255.0 — маска подсети, а 192.168.0.1 — нет.

Поясним, как получается двоичное представление IP-адреса. Для этого числа, составляющие IP-адрес, представляются в двоичной системе счисления (при этом каждое из них дополняется ведущими нулями до длины в 8 цифр), после чего удаляются точки. Получившееся 32-битное число и есть двоичное представление IP-адреса. Например, для адреса 192.168.0.1 этот процесс выглядит так: 192.168.0.1 → 11000000.10101000.00000000.00000001 → 11000000101010000000000000000001. Таким образом, двоичным представлением IP-адреса 192.168.0.1 является 11000000101010000000000000000001.

Будем говорить, что два компьютера с IP1 и IP2 лежат в подсети, если IP1 /\ Mask = IP2 /\ Mask, где Mask — маска этой подсети, а /\ — операция побитового логического «и». IP компьютера представляет собой так же 4 однобайтных числа, разделенных точкой.

Вам даны M пар IP адресов компьютеров. Для каждой из них Вам надо определить, в скольких подсетях из заданных они лежат.

Входные данные

В первой строке входного файла INPUT.TXT записано число N — количество подсетей. В следующих N строках перечислены маски этих подсетей. В N + 2 строке находится число M (0 ≤ M ≤ 10000). В следующих M строках записаны пары IP адресов, разделенных пробелом.

Выходные данные

Для каждой пары IP адресов в отдельной строке выходного файла OUTPUT.TXT выведите количество подсетей, в которых лежат оба компьютера.

Пример

INPUT.TXTOUTPUT.TXT
12
255.255.255.255
255.255.255.0
3
192.168.31.1 192.168.31.2
192.168.31.3 192.168.31.4
192.168.31.1 192.167.31.2
1
1
0

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483