Задача D. (20081220) Мультиплексор

Автор:Жюри зимних сборов 2009   Ограничение времени:2 сек
Входной файл:multiplexor.in   Ограничение памяти:256 Мб
Выходной файл:multiplexor.out  
Максимальный балл:50  

Условие

Мультиплексор в TestSys — это программа для одновременной организации контестов в разных местах с использованием TestSys. Например, если в одно и то же время проходят тренировки в Петергофе и Санкт-Петербурге, самый простой способ их организовать — с помощью мультиплексора. Тренировки по интернету тоже проводятся при помощи мультиплексора.

В этой задаче вам предстоит реализовать часть функциональности мультиплексора. Программа должна прочитать конфигурационный файл и, далее, определить место назначения для каждого входящего пакета.

Конфигурационный файл мультиплексора состоит из нескольких разделов. Описание каждого раздела соответствует одному порту. Заголовок раздела состоит из одной строки вида:

A.port

где port — произвольное целое число между 0 и 65 535, а `.' означает произвольное количество пробелов (ASCII-код 32) и табуляций (ASCII-код 9). Для каждого порта определены некоторые правила. Описание каждого правила находится на отдельной строке, выглядящей так:

F.from.T.to[.I.id list][.P.password]

Квадратные скобки означают «может быть опущено», как и обычно. Параметр from может быть либо в форме IP , либо в форме IP/mask. В этой задаче IP всегда выглядит как a.b.c.d, где a, b, c и d — любые целые числа в интервале 0..255. mask — это целое число между 0 и 32, интерпретируется следующим образом. Каждый IP-адрес можно рассматривать как 32-битное двоичное число: a соответствует битам с 31 по 24 (старшие), b — битам с 23 по 16, c — с 15 по 8, d — с 7 по 0 (младшие). Эти биты записаны в обычном порядке, то есть, например, старший бит a является старшим битом всего числа, а младший бит d является младшим битом всего числа. Например, адрес 195.19.228.2 будет соответствовать двоичному числу 110000110001001111100100000000102=0xC313E402=3272860674 (или 1022106622, если рассматривать знаковый тип). Значение маски определяет количество значимых старших битов адреса. Остальные биты могут быть произвольными. Например, под 195.19.228.2/24 подходит любой адрес, начинающийся на 195.19.228 («195.19.228.*»), а 195.19.228.2/20 означает, что адрес должен быть в интервале 195.19.224.0--195.19.239.255. Если параметр mask опущен, маска считается равной 32 (все биты значимые). Пакет подходит под правило, если источник пакета находится в указанном диапазоне. Есть ещё три условия для того, чтобы пакет подошёл под правило. Во-первых, конечно, пакет должен быть получен через порт port, который указан в заголовке раздела. У всех разделов указаны разные порты. Ещё два правила — это правила соответствия идентификатора и пароля. Правило соответствия пароля очень простое: пароль, содержащийся в правиле, должен совпадать (с учётом регистра) с паролем к правилу (если правило не содержит пароля, любой принимается, если в пакете нету пароля, он принимается только в случае отсутствия пароля у правила). Пароль всегда состоит из не более, чем 64 букв и цифр. Правило соответствия идентификатора несколько сложнее. id list может иметь вид id или firstid-lastid. В первом случае необходимо точное совпадение id и id, указанного в пакете (с теми же оговорками, что и в правиле соответствия пароля, аналогично, идентификатор состоит из не более, чем 64 букв и цифр). Во втором случае firstid и lastid должны быть целыми числами одинаковой длины (ведущие нули разрешены). Пакет удовлетворяет правилу, если идентификатор, указанный в пакете имеет ту же длину, что и firstid и lastid, является числом и лежит между firstid и lastid включительно. Длины этих чисел во входном файле никогда не будут больше пяти. В случае, когда пакет удовлетворяет всем четырём условиям, он должен быть направлен хосту to, где to — IP-адрес (IP). Правила проверяются в порядке их следования. Как только найдено удовлетворяющееся правило, пакет немедленно перенаправляется и система переходит к обработке следующего пакета. Если пакет не подходит ни под одно правило, он перенаправляется в NULL device (то есть игнорируется).

Формат входного файла

Входной файл начинается с нескольких строк, описывающих конфигурацию мультиплексора. После последнего раздела идёт разделяющая строка, состоящая из трёх дефисов («---»). После этого начинаются пакеты. Пакеты описываются в том же виде, что и правила, с тремя исключениями: во-первых, в адресе источника не разрешается маска (mask), во-вторых, адрес назначения отсутствует (поскольку мы знаем, что этот пакет для нас), параметр to содержит номер порта, на который пришёл пакет, в-третьих, идентификатор не может быть указан в виде диапазона (firstid-lastid). В файле нет пустых строк. Количество разделов не менее одного и не более 32, и для каждого порта определено не менее одного и не более 32 правил. Количество пакетов не превышает 3000.

Формат выходного файла

Для каждого пакета выведите на отдельной строке адрес, на который его надо перенаправить. Если пакет перенаправлен в NULL device, выведите /dev/null вместо адреса.

Примеры тестов

Входной файл (multiplexor.in) Выходной файл (multiplexor.out)
1
A       12345
F       192.168.64.90/24   T       195.19.228.2
F       195.19.228.2       T       192.168.64.90   I       00-29
A       13456
F       195.19.228.2/28    T       195.19.228.213  P       passwd
F       0.0.0.0/0          T       195.19.228.2    I       ttt     P       secret
A       23917
F       1.2.3.4            T       195.19.228.2    I       1
{-}{-}{-}
F       192.168.64.239     T       12345           I       abc
F       192.168.65.0       T       12345
F       195.19.228.2       T       12345           I       1
F       195.19.228.2       T       12345           I       23      P       super
F       1.2.3.4            T       23917           I       01
F       1.2.3.4            T       23917           I       1
F       1.2.3.4            T       23917
F       195.19.228.16      T       13456           P       passwd
F       195.19.228.16      T       13456           I       ttt     P       passwd
F       195.19.228.16      T       13456           I       ttt     P       secret
F       195.19.228.15      T       13456           P       passwd
F       195.19.228.15      T       13456           I       ttt     P       passwd
195.19.228.2
/dev/null
/dev/null
192.168.64.90
/dev/null
195.19.228.2
/dev/null
/dev/null
/dev/null
195.19.228.2
195.19.228.213
195.19.228.213

0.095s 0.012s 13