Marşrutlaşdırma
Müasir şəbəkələrdə, şəbəkə paketlərinin marşrutlarını təyin etmək üçün marşrutlaşdırıcılar adlanan xüsusi cihazlardan istifadə olunur. Bu cihazlar marşrutlaşdırma cədvəlinə əsaslanaraq işləyir. Marşrutlaşdırma cədvəli, marşrutları təsvir edən bir neçə sətirdən ibarətdir. Hər bir sətir 3 sahədən ibarətdir: D, M və G. Burada D təyinat şəbəkəsinin IP ünvanını, M maskanı, G isə şlüzün IP ünvanını göstərir (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, 192.168.24.0 şəbəkəsinə 255.255.255.0 maskası ilə ünvanlanmış paketin 192.168.14.1 şlüzü vasitəsilə göndərilməli olduğunu bildirir.
Qısa məlumat. IP ünvanı 32-bitlik bir ədəddir və rahatlıq üçün onluq-nöqtəli formatda yazılır, yəni hər bir bayt onluq şəkildə təqdim olunur və aralarında nöqtələr qoyulur. Məsələn, 192.168.24.0 yazısı 11000000101010000001100000000000 ikilik ədədini ifadə edir. Maskalar üçün də bu qayda keçərlidir. Maskaların mühüm xüsusiyyəti odur ki, ikilik təqdimatda maskalarda əvvəlcə yalnız birlər, sonra isə yalnız sıfırlar gəlir. Şlüz ünvanı tamamilə sıfır və ya bir bitlərdən ibarət ola bilməz.
Marşrut seçimi alqoritmi belə işləyir: Tutaq ki, A ünvanına yönəlmiş bir paket var. Əvvəlcə marşrutlaşdırıcı bütün qeydləri nəzərdən keçirir və yalnız D and M = A and M şərtini ödəyən qeydləri saxlayır (and — bit-bit "VƏ" əməliyyatı). Sonra bu qeydlərdən maskada bir bitlərinin sayı maksimum olanı seçilir — bu, nəticə olacaq. İstənilən ünvan üçün belə qeydlərin həmişə birdən çox olmayacağı təmin edilir.
Cədvəlin ölçüsü nə qədər böyükdürsə, marşrutlaşdırıcı bir o qədər yavaş işləyir və daha çox resurs istehlak edir. Lakin bir çox hallarda verilmiş cədvəl ekvivalent, lakin daha az sətirə malik 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 isə 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, bu iki cədvəl üzrə istənilən təyinat ünvanı üçün eyni şlüz müəyyən 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-bitlik ədəd ola bilər (yəni real şəbəkələrdə olduğu kimi xüsusi və icazəsiz ünvanlar yoxdur).
Böyük ölçülü cədvəlləri əl ilə müqayisə etmək olduqca çətindir. Sizdən iki verilmiş cədvəlin ekvivalentliyini yoxlamaq üçün proqram yazmaq tələb olunur.
Giriş verilənləri
Giriş faylının ilk sətirində birinci marşrutlaşdırma cədvəlindəki qeydlərin sayı olan N tam ədədi ( 1 ilə 100 000 arasında) yazılmışdır. Növbəti N sətir yuxarıda təsvir olunan formatda marşrutlaşdırma cədvəlini ehtiva edir. Sonra ikinci cədvəldəki qeydlərin sayı olan M tam ədədi ( 1 ilə 100 000 arasında) yazılmışdır. Növbəti M sətir ikinci marşrutlaşdırma cədvəlini ehtiva edir.
Çıxış verilənləri
Çıxış faylının ilk sətirində YES və ya NO sözünü yazın.