Mühafizəçilər#4028
Qədim bir krallıqda kral qalaları, sülalənin ilk kralı Sane'nin dizaynına uyğun olaraq inşa edilmişdir. O, "böl və idarə et" prinsipinə əsaslanaraq hökmranlıq edirdi. Buna görə də, bütün qalalar bir-birinə bağlı binalardan ibarət iyerarxik bir naxışla tikilmişdir. Hər bina, zallar və bu zalları birləşdirən dəhlizlərdən ibarətdir.
Əvvəlcə, qala yalnız bir binadan (əsas bina) ibarətdir. Əhali artdıqca, qala aşağıdakı şəkildə genişlənir: Mövcud binalardan birinə yeni bir periferik bina əlavə edilir. Hər yeni bina da digər binalar kimi zallar və dəhlizlərdən ibarətdir. Mövcud binadakı bir zalı yeni binadakı bir zala birləşdirən əlavə bir dəhliz yaradılır. Bu dəhliz yeni binaya girişin yeganə yoludur.
Bir binadakı zalların sayı maksimum -dur.
Şəkil 1: Aşağıda verilmiş nümunənin qala planı.
Çətinlik dövrlərində kral, zallara strateji şəkildə gözətçilər yerləşdirərək bütün dəhlizləri nəzarətdə saxlayır. O, sizdən qaladakı bütün dəhlizləri nəzarətdə saxlamaq üçün lazım olan ən az sayda gözətçini müəyyən etməyinizi istəyir (çünki o, şəxsi gözətçisini mümkün qədər böyük saxlamaq istəyir). Qeyd edək ki, son yanğından bəri qalada qapılar yoxdur, buna görə də bir zala yerləşdirilən gözətçinin bütün birləşdirici dəhlizləri nəzarətdə saxlaya biləcəyini təhlükəsiz şəkildə qəbul edə bilərik.
Giriş bir neçə qala təsvirini ehtiva edir. Bir qalada, hər bir zal ilə arasında unikal bir nömrə ilə müəyyən edilir. Hər bir qala, əsas binanın təsviri ilə başlayaraq rekursiv şəkildə müəyyən edilir:
Üç tam ədəd olan bir sətir, bu binadakı zalların sayını (2 \leq n \leq 10), bu binadakı dəhlizlərin sayını (1 \leq m \leq 45) və sonradan bu binaya əlavə edilmiş periferik binaların sayını (0 \leq w \leq 10) təmsil edir.
dəhlizlərinin hər biri üçün:
İki tam ədəd olan bir sətir (hər biri \leq 10\,000), bu dəhlizin birləşdirdiyi iki zalı təmsil edir. Hər iki zal cari binanın içərisində yerləşir.
periferik binaların hər biri üçün:
Bu periferik binaya aparan dəhlizi təsvir edən iki tam ədəd olan bir sətir. Birinci ədəd cari binadakı bir zalı, ikinci ədəd isə periferik binadakı bir zalı təmsil edir.
Periferik binanın quruluşu və sonradan ona əlavə edilmiş hər hansı yeni binalar, qaydalar 1 ilə 3 təkrarlanaraq təsvir edilir.
Qala tam bağlıdır: hər hansı bir zal digər hər hansı bir zaldan birbaşa və ya dolayı yolla əldə edilə bilər. Eyni başlanğıc və son zalı olan dəhlizlər mövcud deyil və hər iki zal arasında ən çox bir dəhliz var.
Hər qala üçün, bütün dəhlizlərin nəzarətdə saxlanılması üçün zallara yerləşdiriləcək minimum gözətçi sayını ehtiva edən bir müsbət tam ədəd olan bir sətir çap edin.
Nümunə 1