루미 알고리즘

#1404플래티넘Brandvägg

PO 2016 온라인 예선코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

On the Internet, there are many bad guys who always try to hack the computers of others. They steal cat pictures, bank logins and membership lists on programming dating sites. One of the first countermeasures against network-based attacks is the firewall. A firewall filters some network trafik based on different criteria, to shut out unauthorized access. In this problem, we are going to code the part of the firewall that determines of a certain message sent to a server over a network should be dropped or accepted.

A firewall consists of a number of rules in a long list. A rule is on the form “if [list of conditions] are true, perform an action”. These conditions are one of

  • port=XYZ - if the message was sent to port XYZ.
  • ip=XYZ - if the message was sent from the IP-address XYZ.
  • limit=XYZ - if at least XYZ of the last 1000 messages (including the one just received) was sent from this IP-address.

and the actions are one of

  • accept - let the package through the firewall. Print accept packet-ID.
  • log - print log packet-ID.
  • drop - block the packet. Print drop packet-ID.

Some examples of rules with explanations:

  • accept - always accept the packet.
  • accept ip=127.0.0.1 - accept the packet if it comes from the IP-address 127.0.0.1.
  • drop port=22 ip=192.168.1.1 - drop the packet if its from the IP-address 192.168.1.1 and sent to port 22.
  • log port=80 limit=500 - log the packet if it was sent to port 80, and at least half of the last 1000 messenges was sent from this IP-address.

When a packet enters the firewall, it looks at every rule in the list, top to bottom, until it reaches a rule that matches the packet. The given firewall will always be constructed such that a packet will be accepted or dropped before the end of the list.

Input

The first line of input contains an integer 1 ≤ N ≤ 100, the number of rules in the firewall.

The next N lines contains the rules in the list, one rule on each line.

The next row contains an integer P ≤ 10000, the number of packets arriving to the firewall. They are given in the order of arrival. A packet is on the form IP:port, for example 127.0.0.1:123. The packet ID is just the position of the packet in this list. The first packet has id 1 and the last ID P.

A port is an integer 1 ≤ p ≤ 65535.

Output

For each packet, you are to run it through the firewall until it is accepted or dropped. Each action that is taken describes what to print. Note that since the action log doesn't stop the packet in the firewall, each packet could result in multiple lines of output.

Scoring

Your solution will be tested on a number of test case groups. To get points for a group you have to solve all the test cases in that group.

GroupPointsLimits
17P ≤ 10000. There are only accept actions.
215P ≤ 10000. No rule has a condition.
329P ≤ 10000. There are no limit conditions.
425P ≤ 100
514P ≤ 1000
610P ≤ 10000

예제

예제 1

입력
6
accept ip=127.0.0.1
drop port=22
accept limit=5
accept port=80
accept port=10 port=11
drop
16
127.0.0.1:80
127.0.0.1:22
192.168.0.1:80
192.168.0.1:11
192.168.0.1:12
192.168.0.1:13
192.168.0.1:14
192.168.0.1:15
192.168.0.1:16
192.168.0.1:22
192.168.0.1:80
154.135.0.5:22
154.135.0.5:80
127.0.0.1:8080
215.215.5.8:5919
215.215.5.9:5919
출력
accept 1
accept 2
accept 3
drop 4
drop 5
drop 6
accept 7
accept 8
accept 9
drop 10
accept 11
drop 12
accept 13
accept 14
drop 15
drop 16

예제 2

입력
4
accept ip=192.168.0.1
log port=22
accept
drop
16
127.0.0.1:80
127.0.0.1:22
192.168.0.1:80
192.168.0.1:11
192.168.0.1:12
192.168.0.1:13
192.168.0.1:14
192.168.0.1:15
192.168.0.1:16
192.168.0.1:22
192.168.0.1:80
154.135.0.5:22
154.135.0.5:80
127.0.0.1:8080
215.215.5.8:5919
215.215.5.9:5919
출력
accept 1
log 2
accept 2
accept 3
accept 4
accept 5
accept 6
accept 7
accept 8
accept 9
accept 10
accept 11
log 12
accept 12
accept 13
accept 14
accept 15
accept 16

예제 3

입력
5
log limit=1
log limit=2
log limit=3
drop limit=1
accept
16
127.0.0.1:80
127.0.0.1:22
192.168.0.1:80
192.168.0.1:11
192.168.0.1:12
192.168.0.1:13
192.168.0.1:14
192.168.0.1:15
192.168.0.1:16
192.168.0.1:22
192.168.0.1:80
154.135.0.5:22
154.135.0.5:80
127.0.0.1:8080
215.215.5.8:5919
215.215.5.9:5919
출력
log 1
drop 1
log 2
log 2
drop 2
log 3
drop 3
log 4
log 4
drop 4
log 5
log 5
log 5
drop 5
log 6
log 6
log 6
drop 6
log 7
log 7
log 7
drop 7
log 8
log 8
log 8
drop 8
log 9
log 9
log 9
drop 9
log 10
log 10
log 10
drop 10
log 11
log 11
log 11
drop 11
log 12
drop 12
log 13
log 13
drop 13
log 14
log 14
log 14
drop 14
log 15
drop 15
log 16
drop 16

출처 표기

출처: Programmeringsolympiaden 2016년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.