Задача №112534. Маски подсети
Рассмотрим компьютерную сеть с настроенной 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.
Будем говорить, что два компьютера с IP 1 и IP 2 лежат в подсети, если IP 1 & Mask = IP 2 & Mask , где Mask — маска этой подсети, а & — операция побитового логического "и". IP компьютера представляет так же 4 однобайтных числа, разделенных точкой.
Вам даны M пар IP-адресов компьютеров. Для каждой из них Вам надо определить, в скольких подсетях из заданных они лежат.
В первой строке входного файла записано число N — количество подсетей. В следующий N строках перечислены маски этих подсетей. В N + 2 строке находится число M (0 ≤ M ≤ 100000) . В следующих M строках записаны пары IP-адресов, разделенных пробелом.
Все заданные маски подсетей различны.
Для каждой пары IP-адресов в отдельной строке выходного файла выведите количество подсетей, в которых лежат оба компьютера.
2 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