Županijsko NATJECANJE 2015 / Srednja škola, II. podskupina (3. i 4. razred) - 1. zadatak

U računalnim mrežama važnu ulogu igra takozvana tablica usmjeravanja na temelju koje se određuje sljedeći usmjernik (router) na koji treba poslati paket s podacima dok on putuje mrežom.

U ovom zadatku potrebno je simulirati pojednostavljenu tablicu usmjeravanja za IPv4 protokol.

Adresa u IPv4 protokolu je 32-bitni binarni broj koji se obično zapisuje tako da se podijeli u četiri 8-bitna broja te se ta četiri broja pretvore u dekadski sustav i zapišu s lijeva na desno odvojeni točkama.

Tako je, na primjer, 18.62.0.96 zapis adrese 00010010 00111110 00000000 01100000 (razmaci su umetnuti samo za lakše čitanje).

Maska je također 32-bitni binarni broj koji se zapisuje na isti način kao i adresa.

Podmreža je skup adresa koji se opisuje pomoću jedne adrese i jedne maske.

Podmreža sadrži točno sve one adrese koje se podudaraju s adresom podmreže na onim bitovima na kojima maska podmreže ima vrijednost 1.

Ukoliko nas zanima je li adresa X sadržana u podmreži zadanoj adresom D i maskom M, to možemo odrediti tako da binarne brojeve D, M i X napišemo poravnate jedan ispod drugog te provjerimo jesu li D i X isti na svim pozicijama na kojima M ima jedinicu.

Primjer dvaju podmreža zajedno s adresama koje njima pripadaju dan je u sljedećoj tablici:

Tablica usmjeravanja daje nam niz pravila koja određuju na koji je usmjernik potrebno poslati paket na temelju adrese odredišta paketa. Svako je pravilo prikazano u obliku trojke D, M, S gdje su D i M adresa i maska podmreže, a S prirodni broj između jedan i 100 koji označava usmjernik na koji je potrebno poslati paket u slučaju da je adresa odredišta paketa sadržana u toj podmreži.

Dakle, kako bismo odredili sljedeći usmjernik na koji je potrebno poslati paket s određenom odredišnom IP adresom X, redom prolazimo kroz tablicu te kada nađemo prvu podmrežu koja sadrži adresu X paket šaljemo prema tom usmjerniku.

Napišite program koji će za zadanu tablicu usmjeravanja i niz paketa koji se šalju mrežom, za svaki paket odrediti oznaku usmjernika prema kojemu ga treba slati.

Ulazni​ podaci

U prvom redu nalaze se prirodni brojevi N i Q (1 ≤ N ≤ 100, 1 ≤ Q ≤ 100) - broj pravila u tablici i broj paketa.

U svakom od sljedećih N redova nalazi se jedno pravilo usmjeravanja.

Svako pravilo se sastoji od adrese podmreže D, maske podmreže M te oznake usmjernika S odvojenih jednim razmakom.

Adresa i maska podmreže su nizovi znakova sastavljeni od točno četiri dekadska broja između 0 i 255 odvojena točkama.

Oznaka usmjernika S je prirodni broj manji ili jednak od 100.

Nakon toga u Q redova slijede adrese odredišta paketa.

Ulaz će biti takav da je adresa odredišta svakog paketa sadržana u barem jednoj podmreži među pravilima.

Izlazni podaci

Potrebno je ispisati Q redova.

U K-ti redak potrebno je ispisati oznaku usmjernika prema kojem treba poslati K-ti po redu paket iz ulaza.

Primjeri test​ podataka

Ulaz

2 1
192.168.0.1 255.255.255.255 11
192.168.0.0 255.255.255.255 4
192.168.0.0

Izlaz

4

Ulaz

4 3
255.168.0.1 192.255.0.64 7
192.168.0.0 192.255.0.64 9
192.168.0.0 63.87.255.255 10
0.0.0.32 65.16.48.32 3
192.168.0.0
128.239.0.255
0.0.0.0

Izlaz

7
3
10