Zuma Oyunu
Bəziləriniz Zuma adlı qurbağanın macəralarını əks etdirən oyunu tanıya bilərsiniz. Bu məsələdə qaydalar oxşardır və olduqca sadədir: daşdan hazırlanmış novda müxtəlif rəngli toplar yerləşir; novun yanında yerləşən top atan cihaz müəyyən miqdarda müxtəlif rəngli topları saxlayır və bu topları vaxtaşırı novun içinə atır. Atılan toplar sıraya düzülür. Əgər atışdan sonra novda üç və ya daha çox eyni rəngli topdan ibarət ardıcıl bir sıra yaranarsa, atılan top da daxil olmaqla, onlar yox olur və qonşu toplar sıxlaşaraq sıranı bağlayır (aşağıdakı şəkilə baxın). Əgər topların yox olmasından sonra qonşu toplar üç və ya daha çox eyni rəngli topdan ibarət ardıcıl bir sıra yaradırsa, onlar da yox olur və bu proses belə davam edir. Oyunun məqsədi bütün topları məhv etməkdir.
Topları soldan sağa doğru, birincidən başlayaraq nömrələyək. Topun n mövqeyinə atılması, onun n nömrəli topun sağında yerləşəcəyini və n+1 mövqeyində olacağını bildirir. Atılan topun sağında yerləşən topların nömrələri bir vahid artır. Sıranın ən soluna topun enməsi 0 nömrəli mövqe ilə göstərilir. Bəzi toplar yox olduqdan sonra, novdakı toplar yenidən soldan sağa doğru, birincidən başlayaraq nömrələnir.
Optimal atış strategiyasını müəyyən edən bir proqram yazmaq lazımdır. Optimal strategiya, ən az sayda atışla bütün topların yox olmasına səbəb olan strategiyadır və əgər belə strategiyalar bir neçədirsə, ilk atışın mümkün qədər sola edildiyi seçilir, əgər belə bir neçə varsa, ikinci atışa görə müqayisə edilir və s.
Giriş verilənləri
Birinci sətir testlərin sayını ehtiva edir. Hər bir test bir sıra topun təsvirindən ibarət bir sətirdən ibarətdir, hər bir topun rəngi böyük latın hərfi ilə təsvir olunur (A..Z). Test №1 və onun həlli şəkildə göstərilmişdir. Məlumdur ki, sıranın uzunluğu ≤ 14, və sıranın məhv edilməsi üçün ≤ 10 atış tələb olunur, əgər optimal strategiyaya əməl edilərsə.
Çıxış verilənləri
Hər bir test üçün bir sətir çıxarın: əvvəlcə minimal atış sayını, sonra isə boşluqla ayrılmış hərf-rəqəm cütlərini: topun rəngi və atış mövqeyi. Cavabda atışlar oyunda icra edilmə sırasına uyğun olaraq sadalanmalıdır.