Brandvägg
På Internet finns många elaka typer som försöker hacka andras datorer i tid och otid. De stjäl kattbilder, bankinloggningar och medlemslistor på programmerares dejtingsidor. En av de första åtgärderna man kan sätta in mot attacker över nätet är brandväggen. En brandvägg filtrerar nätverkstrafik baserat på olika kriterier, för att försöka stänga ute obehöriga. I detta problem ska vi skriva den delen av en brandvägg som avgör om ett visst meddelande som inkommer till en server över ett nätverk ska blockeras (“droppas”) eller inte (“accepteras”).
En brandvägg består av ett antal regler i en lång lista. En regel är på formen “om [lista av villkor] alla är sanna, utför en handling”. Villkoren är på formen
- port=XYZ
-
- om meddelandet skickats till port XYZ.
- ip=XYZ
-
- om meddelandet skickats från IP-addressen XYZ.
- limit=XYZ
-
- om minst XYZ av de senaste 1000 meddelandena (inkluderat det som just kom) skickats från denna IP.
och handlingarna är en av
- accept
-
- släpp genom paketet i brandväggen. Skriv ut accept paket-ID.
- log
-
- skriv ut log paket-ID.
- drop
-
- blockera paketet. Skriv ut drop paket-ID.
En regel skulle alltså kunna se ut som:
- accept
-
- acceptera paketet ovillkorligen.
- accept ip=127.0.0.1
-
- acceptera paketet om det kommer från IP-addressen 127.0.0.1.
- drop port=22 ip=192.168.1.1
-
- droppa paketet om det kommer från IP-addressen 192.168.1.1 och skickas till port 22.
- log port=80 limit=500
-
- logga paketet om det skickas till port 80, och hälften av de senaste 1000 meddelandena skickades från denna IP-address.
När ett paket kommer in i brandväggen tittar man på alla regler i listan upifrån och ned, tills man når en regel som matchar paketet. Den givna brandväggen kommer alltid vara så att paketet kommer accepteras eller droppas innan listan tar slut.
Input
Den första raden i indatan innehåller ett heltal $1 \le N \le 100$, antalet regler i brandväggen.
De nästa $N$ raderna innehåller reglerna i listan, en regel per rad.
Nästa rad innehåller ett heltal $P \le 10\, 000$, antalet paket som kommer in till brandväggen. De är givna i ordningen de kom in. Ett paket är på formen IP:port, t.ex. 127.0.0.1:123. Paketets ID är bara vilken position paketet har i listan. Det första paketet har ID $1$ och det sista har ID $P$.
En port är ett heltal $1 \le p \le 65535$.
Output
För varje paket ska du köra det genom brandväggen. Varje handling som utförs beskriver vad du ska skriva ut. Notera att eftersom handlingen log inte avbryter paketets färd genom listan med regler kan ett paket ge upphov till mer än en utskrift.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Begränsningar |
|
1 |
7 |
$P \le 10\, 000$. Det finns bara accept-handlingar. |
|
2 |
15 |
$P \le 10\, 000$. Ingen regel har något villkor. |
|
3 |
29 |
$P \le 10\, 000$. Det finns inga limit-villkor. |
|
4 |
25 |
$P \le 100$ |
|
5 |
14 |
$P \le 1\, 000$ |
|
6 |
10 |
$P \le 10\, 000$ |
| Sample Input 1 | Sample Output 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 |
| Sample Input 2 | Sample Output 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 |
| Sample Input 3 | Sample Output 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 |
