Warp Sürəti

Yaxın gələcəkdə kosmik mühəndislər yeni bir texnologiya ixtira edə bilər və bunu "warp-drive" adlandıra bilərlər. Warp-drive bir kosmik gəminin işıq sürətindən daha sürətli hərəkət etməsinə şərait yaradır: gəmi kosmosun müəyyən bir hissəsini əyərək o məsafəni bir "tullanış"da keçir. Hər tullanış eyni qədər vaxt apardığı üçün, warp-drive ilə təchiz olunmuş bir kosmik gəminin ümumi səyahət müddəti etdiyi tullanışların sayından asılıdır. Mühəndislər həmçinin müşahidə ediblər ki, hopun məsafəsi həmin anda mövcud olan bəzi qüvvə sahələrindən asılı olur. Başlanğıcdan sona gedən bir yol üçün gəmi bir neçə qüvvə sahəsinin içindən keçməli və çoxlu tullanış etməli ola bilər.

Onlar təcrübələrində aşağıdakı faktları aşkar ediblər:

• Qüvvə sahələrinin növü çox deyil.

  • Ona görə də, hər qüvvə sahəsini bir ingilis hərfi ilə adlandırmaq olar.

• Kosmik gəmi hər bir qüvvə sahəsindən bir tullanışda keçə bilər.

• Ayrıca, gəmi müəyyən iki və ya daha çox qüvvə sahəsindən ibarət ardıcıllıqlardan bir tullanışda keçə bilər. Belə ardıcıllıqlar tək tullanış üçün qaydalar kimi müəyyən edilir.

  • Bu qaydaların nümunə siyahısı aşağıda göstərilmişdir.

• Bu nümunədə $4$ qayda var və gəmi hər birini bir tullanışda keçə bilər. Birincisi — $\mathbf{ab}$, yəni gəmi $\mathbf{a}$ və $\mathbf{b}$ qüvvə sahəsindən bir tullanışda keçə bilər. İkincisi — $\mathbf{abcd}$; gəmi $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$ və $\mathbf{d}$ ardıcıllığından bir tullanışda keçə bilər.

• Diqqət edin ki, bu nümunədə $\mathbf{abc}$ ardıcıllığı/qaydası yoxdur: gəmi $\mathbf{abcd}$-dən keçə bilsə də, $\mathbf{abc}$-dən bir tullanışda keçə bilmir. Burada $2$ tullanış etməlidir: birinci $\mathbf{ab}$ ardıcıllığını, ikinci isə $\mathbf{c}$ qüvvə sahəsini keçmək üçün.

Məqsəd

Tutaq ki, siz döyüş kosmik gəmisində mühəndissiniz. Sizin vəzifəniz gəminizi kosmosdan mümkün qədər tez keçirməkdir. Sizin gəminizdə marşrut boyunca qüvvə sahələrinin ardıcıllığını müəyyən edə bilən zond cihazı var. Vəzifəni yerinə yetirmək üçün qaydalara və verilmiş istənilən ardıcıllığa əsasən minimum tullanış sayını tapacaq bir proqram yazmalısınız.