Marşrutlaşdırma
Siz Inane Collaboration for Performance Computing şirkətində mühəndis olaraq çalışırsınız və burada kompüterlər üçün bir əlaqə şəbəkəsi dizayn etməkdən məsulsunuz. Şəbəkə 2n - 1 sıra ilə düzbucaqlı bir matris kimi təşkil olunub, hər birində 2^(n−1) açar var. Açar, iki giriş telinə, X və Y, və iki çıxış telinə, X' və Y' malik olan bir cihazdır. Açar söndürüldükdə, X girişindən gələn məlumat X' çıxışına, Y girişindən gələn məlumat isə Y' çıxışına ötürülür. Əgər açar açıqdırsa, X Y' ilə və Y X' ilə birləşdirilir. Əlavə olaraq, ən üst və ən alt sıralarda 2n kompüter var və onların arasında mesajlar göndərilməlidir. Fərqli mənbələrdən gələn məlumatlar eyni tel üzərində paylaşa bilməz, lakin hər iki məlumat fərqli girişlərdə eyni açar üzərindən yönləndirilə bilər.
Siz qərara gəlmisiniz ki, məqsədlərinizə ən uyğun olan şəbəkə Benes topologiyasına malikdir. 1-Benes şəbəkəsi sadəcə bir açardır. n > 1 üçün n-Benes şəbəkəsi rekursiv olaraq aşağıdakı kimi qurula bilər:
• İlk (üst) sırada 2^(n−1) açar var, belə ki, açar j (0 ≤ j < 2^(n−1)) 2j və 2j + 1 kompüterlərindən məlumat girişləri alır (ən üst və ən alt sıralardakı kompüterləri soldan sağa doğru 0 və 2^n − 1 arasında tam ədədlərlə etiketləyirik).
• Sonra, ilk və ikinci sıra açarların çıxış tellərinə mükəmməl bir qarışıq permütasiyası tətbiq olunur, yəni bir sıradakı j nömrəli çıxış növbəti sıradakı j' nömrəli girişə bağlanır, burada j' j-nin ikilikdə n bitlik nümunəsinin bir bit sağa döndərilməsi ilə əldə edilir (yenə də girişlər və çıxışlar soldan sağa doğru nömrələnir).
• Əgər n > 2-dirsə, sonuncudan bir əvvəlki sıraya qədər olan növbəti açar sıraları, biri sol tərəfdə və digəri sağ tərəfdə olmaqla iki (n - 1) - Benes alt şəbəkəsi təşkil edir.
• Nəhayət, çıxışlara tərs qarışıq permütasiyası tətbiq olunur və son bir sıra açar əlavə edilir.
Məsələn, yuxarıdakı şəkil n = 3 üçün Benes şəbəkəsini göstərir (kvadratlar açarları təmsil edir; ən üst və ən alt sıralardakı kompüterlər çəkilməyib, lakin 0-dan 7-ə qədər tam ədədlərlə təyin olunub). Şəkil açarların mümkün bir vəziyyətini göstərir, iki xəttin kəsişdiyi kvadratlar açıq olan açarları göstərir. Bu vəziyyətin kompüterlərdən 0, 1, 2, 3, 4, 5, 6, 7-dən aşağıda 3, 7, 4, 0, 2, 6, 1, 5-ə yuxarıda eyni vaxtda əlaqə yollarını qurmağa imkan verdiyini təsdiq edə bilərsiniz.
Sizə eyni vaxtda birləşdirilməsi lazım olan kompüter cütləri (a, b) verilir (burada a alt sıradakı kompüter və b üst sıradakı kompüterdir) və bu, tel-ayrılmış yollar vasitəsilə həyata keçirilməlidir, və siz bütün açarların vəziyyətini seçməlisiniz ki, bu mümkün olsun.
Giriş
Hər bir test halının ilk sətri bir tam ədəd n (1 ≤ n ≤ 13) olacaq, yəni yuxarıda təsvir edildiyi kimi 2^n kompüter cütünü birləşdirməlisiniz. n = 0 olan bir sətir girişin sonunu göstərir və işlənməməlidir.
n > 0 olan hər bir sətir 2^n tam ədəd ehtiva edən başqa bir sətirlə izlənəcək. i-ci tam ədəd (0 ≤ i < 2^n) alt sıradakı i-ci kompüterin əlaqə qurmalı olduğu ən üst sıradakı kompüter olacaq.
Çıxış
Hər bir hal üçün çıxış 2n - 1 sətir olmalıdır, hər biri 2^(n−1) uzunluğunda bir ikilik sətir ehtiva etməlidir, hər bir açarın açıq (1) və ya bağlı (0) olması lazım olduğunu göstərir.
Verilən giriş həmişə ən azı bir həllə malik olacaq. Bir neçə həll olduğu halda, leksikoqrafik olaraq ən kiçik olanı qaytarın. Yəni, üst sıradakı sətir leksikoqrafik olaraq ən kiçik olmalıdır; bərabərlik halında, ikinci sıradakı sətir leksikoqrafik olaraq ən kiçik olmalıdır və s.
Fərqli test hallarının çıxışları arasında boş bir sətir ilə ayrılmalıdır.