Şərif Super Kompüter
SSC, Şərif Universitetində dizayn edilmiş super kompüterdir və 2 "master" və n "slave" prosessorlarına malikdir. Bu sistem proqram təminatını paralel şəkildə işlədə bilir: Master prosessorlardan biri proqram təminatını slave prosessorlarına yükləyir ki, onların arasında yaddaş və CPU istifadəsi balanslaşdırılsın, digər master isə sistemi izləmək üçün istifadə olunur.
Proqram təminatının müxtəlif hissələri arasındakı asılılıqlar səbəbindən prosessorlar arasında çoxlu mesajlar mübadiləsi aparılmalıdır. Mesaj ötürmə yüklənməsini minimuma endirmək üçün çox sürətli şəbəkə lazımdır. Şəbəkəni optimallaşdırmaq üçün hər bir prosessor cütü arasında birbaşa rabitə kabeli olan klik strukturu qurulacaq.
İki fərqli kabel var: mavi kabellər saniyədə 100 Megabitə qədər ötürə bilər və qırmızı kabellər saniyədə 1 Gigabitə qədər ötürə bilər. Hər bir slave prosessor cütü bir mavi kabel ilə bağlanacaq. Master prosessorlar üzərində daha yüksək rabitə həcmi səbəbindən iki master bir qırmızı kabel ilə və həmçinin hər bir master hər bir slave ilə başqa bir qırmızı kabel ilə bağlanır.
Beləliklə, SSC n+2 ana platalardan ibarətdir, hər biri dəqiq bir prosessor, lazım olan yaddaş və həmçinin üfüqi sıra şəklində quraşdırılmış n+1 oxşar şəbəkə yuvası ehtiva edir. Ana platalar şaquli rəf qutusuna yerləşdirilir, hər biri bir üfüqi rəfdə. Beləliklə, hər bir ana plata rəfdəki hündürlüyü ilə unikal şəkildə müəyyən edilir.
Soyutma sistemi bizi iki master ana platanı rəfin ən aşağı və ən yüksək rəflərinə yerləşdirməyə məcbur edib. Aşağıdakı masterin hündürlüyünün 0 olduğunu və digər ana plataların hündürlüklərinin 0-dan yüksək tam ədədlər olduğunu qəbul edirik. Siz, kompüter mühəndisi olaraq, SSC-nin son montajını həyata keçirmək üçün təyin olunmusunuz. Sizə boş rəf qutusu, hazır ana platalar verilir və sizin işiniz lövhələri məhdudiyyətlərə və kabel uzunluqlarına uyğun olaraq rəfə yerləşdirə biləcəyinizi müəyyən etməkdir.
Dəqiq 2n+1 qırmızı kabel mövcuddur və verilmiş ölçülərdədir. Lakin mavi kabellər m müxtəlif ölçüdə mövcuddur və hər ölçüdə limitsiz sayda kabelimiz var. Siz prosessorlar arasındakı kabelləri səliqəli və sıx saxlamağa çox diqqət edirsiniz, buna görə də ana plataları elə hündürlüklərdə quraşdırmaq istəyirsiniz ki, hər bir ana plata cütü arasındakı kabelin ölçüsü dəqiq iki lövhənin hündürlükləri arasındakı fərqə bərabər olsun.
Giriş verilənləri
Girişdə bir neçə test halı var. Hər test halının ilk sətri iki ədəd n (1 ≤ n ≤ 100) və m (1 ≤ m ≤ 1000) ehtiva edir. İkinci sətr 2n+1 ədəd ehtiva edir, bunlar Gigabit Ethernet kabellərinin ölçüləridir. Üçüncü sətr m ədəd ehtiva edir, bunlar Megabit Ethernet kabel qruplarının ölçüləridir. Girişin son sətri iki sıfır ədəd ehtiva edir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün SSC rəf qutusundakı ana plataların hündürlüklərini n+1 ədəd olaraq yazmalısınız. Birinci ədəd yuxarı master prosessorun hündürlüyünü, qalan n ədədlər isə artan sırada slave-lərin mövqelərini təmsil edir. Bir neçə həll yolu varsa, əlifba sırasına görə ən kiçiyini yazın. Əgər həll yolu yoxdursa, "Impossible" yazın.