Quldurlar#6900
Bir gəmi quldurların hücumuna məruz qalıb. Gəmi ən yaxın donanmadan təxminən 30 dəqiqə uzaqlıqdadır və xilasedicilər gəmini xilas etmək üçün yoldadırlar. Gəminin heyəti təhlükəsiz zonada toplaşıb. Kapitan, quldurların onları girov götürməsinin qarşısını almaq üçün bu zonanı qorumaq istəyir, bu da xilasedicilər üçün vəziyyəti daha da çətinləşdirir. Gəmidə bir neçə qapı ilə birləşdirilmiş çoxlu zona var. Hər bir qapı yalnız bir tərəfdən kilidlənə və açılıb-bağlana bilər. Quldurlar gəminin bəzi zonalarını ələ keçiriblər və kapitan, quldurların təhlükəsiz zonaya daxil olmasının qarşısını almaq üçün minimum sayda qapını kilidləmək istəyir. Məsələn, aşağıdakı vəziyyətdə 7 zonalı bir gəmi təsvir edilmişdir:
Otaqlar 0 ilə 6 arasında nömrələnib və hər qapının bir tərəfində qapının o tərəfdən kilidlənə/açıla biləcəyini göstərən '*' işarəsi göstərilib. Əgər heyət 4-cü zonadadır və bütün quldurlar 5-ci zonadadırsa, heyəti qorumaq üçün kapitan ən azı iki qapını kilidləməlidir, yəni 3 və 5 zonaları arasındakı qapı və 4 və 5 zonaları arasındakı qapı. Qeyd edək ki, 3 və 5 zonaları arasındakı qapı əvəzinə 3 və 4 zonaları arasındakı qapını kilidləmək böyük bir səhvdir, çünki quldurlar 3 və 4 zonaları arasındakı qapını asanlıqla açıb təhlükəsiz zonaya daxil ola bilərlər.
Girişdə bir neçə test halı var. Hər bir test halı iki qeyri-mənfi tam ədəd z və s (0 ≤ z ≤ 20, 0 ≤ s ≤ 19) ilə başlayan bir sətirdən ibarətdir, burada z gəmidəki zonaların sayını və s təhlükəsiz zonanın nömrəsini göstərir. Fərz edək ki, zonalar 0 ilə z−1 arasında nömrələnib. Növbəti z sətirdə, i-ci sətir i−1-ci Zona üçün məlumatları təmsil edir. Hər bir sətir 'P' və ya 'NP' ilə başlayır, burada 'P' zonanın bəzi quldurlar tərəfindən ələ keçirildiyini, 'NP' isə zonanın hələ də təmiz olduğunu bildirir. 'P'/'NP'-dən sonra i−1-ci Zonanın içindən kilidlənə/açıla bilən qapıların sayı gəlir. Sətir bu qapılardan keçilə bilən zonaların siyahısı ilə davam edir. Məsələn, yuxarıdakı nümunədə 5-ci zonanı təmsil edən sətirdə 3 və 4 zonalarını siyahıya daxil etmirik, çünki 3 və 4 zonalarına bitişik qapılar 5-ci zonanın içindən kilidlənə/açıla bilmir. Çıxış "0 0" ilə bitir və bu işlənməməlidir.
Hər bir test halı üçün təhlükəsiz zonanı qorumaq üçün kilidlənməli olan minimum qapı sayını çıxarın. Əgər təhlükəsiz zonanı qorumaq mümkün deyilsə, sadəcə "Sorry Captain!" çıxarın. Fərz edin ki, bütün qapılar əvvəlcə açıqdır və təhlükəsiz zonada heç bir quldur yoxdur.
Nümunə 1