Sürətli Axtarış
Bir polis bölməsi, az sayda zabitlə mümkün qədər tez bir neçə yeri axtarmalı olduqları bir sıra vəziyyətlərlə qarşılaşıb. Şəkil 1 və 2 iki belə vəziyyətin diaqramlarını göstərir. Axtarılacaq yerlər böyük hərflərlə işarələnib. A hərfi ilə işarələnmiş yer ümumi başlanğıc nöqtəsidir. Bu yerlərin bəzilərində birləşdirici yollar mövcuddur. Hər bir birləşdirici yolun keçilməsi bir zaman vahidi çəkir və fərdi yerlərin vizual axtarışı üçün əlavə vaxt tələb olunmur.
Şəkil 1-i nəzərdən keçirin. Əgər 3 və ya daha çox zabit varsa, axtarış yalnız bir zaman vahidi çəkir. Müxtəlif zabitlər AB, AC və AD yollarını izləyirlər. Əgər iki zabit varsa, tam axtarış iki zaman vahidi çəkəcək. Məsələn, bir zabit ABC yolunu, digəri isə AD yolunu izləyə bilər.
Şəkil 2-ni nəzərdən keçirin. Əgər 3 zabit olsaydı, onlar ABC, ABD və AEAF yollarını izləyə bilərdilər və 3 zaman vahidi çəkərdilər. 2 zabitlərlə isə ABCBD və AEAF yollarını izləyərək 4 zaman vahidi çəkərdilər.
Bunlar əl ilə həll edilə biləcək qədər sadə nümunələrdir. Daha mürəkkəb vəziyyətlər üçün proqramlaşdırma köməyinizə ehtiyac duyulur.
Giriş verilənləri
Giriş 1 ilə 25 arasında məlumat dəstlərindən ibarət olacaq və yalnız 0 olan bir sətirlə tamamlanacaq.
Hər bir məlumat dəsti, boşluqla ayrılmış müsbət tam ədədlərlə başlayan s n p tək sətirdən ibarətdir. Burada s axtarılacaq yerlərin sayı, n zabitlərin sayı və p axtarış yerləri arasında birləşdirici yolların sayıdır. Məhdudiyyətlər 2 ≤ s ≤ 10, 1 ≤ n ≤ 4 və p ≤ 20. Sətirin qalan hissəsi, yerlər arasında yolları göstərən, hər biri boşluqla ayrılmış p cüt böyük hərflərdən ibarətdir. Yerlər ilk s böyük hərflərlə işarələnəcək. Bütün yerlər birləşdirici yolların bəzi ardıcıllığı ilə birləşdiriləcək. Hər bir hərf cütündəki iki hərf əlifba sırası ilə artan olacaq. Heç bir hərf cütü təkrarlanmayacaq.
Çıxış verilənləri
Hər bir məlumat dəsti üçün yalnız A yerindən başlayan n zabit üçün minimum axtarış vaxtını ehtiva edən bir çıxış sətri var.
Algoritminizlə diqqətli olun, əks halda həlliniz çox uzun çəkə bilər.
Nümunə giriş məlumat dəstləri müzakirə olunan ssenarilərə uyğundur.