Marşrutlaşdırma#2004
Şəbəkə paketlərinin marşrutlarını təyin etmək üçün müasir şəbəkələrdə xüsusi qurğular — marşrutlaşdırıcılar istifadə olunur. Marşrutlaşdırıcılar marşrutlaşdırma cədvəlinə əsaslanır. Marşrutlaşdırma cədvəli sətirlərdən ibarətdir; hər sətir 3 sahə saxlayır: D, M və G. Burada D təyinat şəbəkəsinin IP ünvanıdır, M maskadır, G isə şlüzün (gateway-in) IP ünvanıdır (qeyd: real cədvəllərdə sahələr daha çox ola bilər). Məsələn, 192.168.24.0 255.255.255.0 192.168.14.1 sətiri bildirir ki, 192.168.24.0 şəbəkəsinə 255.255.255.0 maskası ilə göndərilən paket 192.168.14.1 şlüzü vasitəsilə göndərilməlidir.
Qısa arayış. IP ünvanı 32-bitlik ədəddir. Onun yazılışı rahatlıq üçün dörd bayt onluq şəklində nöqtələrlə ayrılır. Məsələn, 192.168.24.0 yazılışı 11000000101010000001100000000000 ikilik ədədini ifadə edir. Maskalar üçün də bu qayda keçərlidir. Maskaların ən vacib cəhəti odur ki, ikilik təqdimatında əvvəlcə birlər, sonra isə sıfırlar yerləşir. Şlüz ünvanı tamamilə sıfırlardan və ya tamamilə birlərdən ibarət ola bilməz.
Marşrut seçimi alqoritmi belədir: Tutaq ki, paket A ünvanına yönəlib. Marşrutlaşdırıcı bütün qeydləri yoxlayır və yalnız D and M = A and M şərtini ödəyənləri saxlayır (and — bit-bit "VƏ" əməliyyatıdır). Bu qeydlərdən maskada bir olanların sayı ən çox olanı seçilir — nəticə bu qeyd olacaq. Qarantiya olunur ki, istənilən ünvan üçün belə bir qeyd ən çox bir olacaq.
Cədvəl nə qədər böyük olsa, marşrutlaşdırıcı bir o qədər ləng və daha çox resurs istifadə edir. Amma bir çox hallarda verilmiş cədvəl daha az sətirli, ekvivalent bir cədvələ çevrilə bilər.
Məsələn, birinci cədvəl belə ola bilər:
192.168.0.0 255.255.255.0 192.168.14.1
192.168.1.0 255.255.255.0 192.168.14.1
192.168.2.0 255.255.255.0 192.168.14.2
192.168.3.0 255.255.255.0 192.168.14.2
İkinci cədvəl belə ola bilər:
192.168.0.0 255.255.252.0 192.168.14.1
192.168.2.0 255.255.254.0 192.168.14.2
Asanlıqla əmin olmaq olar ki, hər iki cədvəl üçün istənilən təyinat ünvanı üzrə eyni şlüz təyin ediləcək (və ya heç biri müəyyən edilməyəcək). Qeyd edək ki, bu məsələdə təyinat ünvanı istənilən 32-bit ədəd ola bilər (real şəbəkələrdə olduğu kimi xüsusi və ya icazəsiz ünvanlar yoxdur).
Böyük cədvəlləri əl ilə müqayisə etmək çətindir. Sizin vəzifəniz verilmiş iki cədvəlin ekvivalentliyini yoxlayan proqram yazmaqdır.
Giriş faylının birinci sətrində birinci marşrutlaşdırma cədvəlindəki sətirlərin sayı olan N verilmişdir (1 ilə 100,000 arasında). Sonrakı N sətrdə təsvir olunan formatda marşrut cədvəli yerləşir. Sonra ikinci cədvəldəki sətirlərin sayı M (1 ilə 100,000 arasında) verilir. Sonrakı M sətrdə isə ikinci marşrutlaşdırma cədvəli yerləşir.
Çıxış faylının birinci sətrində YES və ya NO sözünü yazın.
Nümunə 1