İstiqamətlər
Tenturda hər kəsin al qırmızı şalvar geyinmək hüququ var, lakin gravitsapa ilə pepelats hər kəsdə olmadığı üçün planetlər arasında səyahət əksər sakinlər üçün əlçatmaz idi. Lakin son zamanlar Pluk planetindən bir çalışqan çatlanan sərnişin daşımaları bazarına çıxıb və bir neçə çatl qarşılığında planetdən planetə getmək istəyənləri daşımağa hazırdır. Uçuş Pluk planetindən başlayır, bir neçə digər planetləri əhatə edir və yenidən Pluk planetində başa çatır. Lakin uçuşun hazırlanması zamanı gözlənilməz problemlər ortaya çıxdı. Məsələn, Pluk planetindən olan bir çatlanan uçuşda sondan əvvəlki planetə getmək istəyirsə, o, istəmədən Pluk planeti ilə təyinat nöqtəsi arasında olan bütün planetləri ziyarət etməli olacaq. Aydındır ki, bu siyahıdakı bəzi planetlər patsak planetləri ola bilər. Lakin hər bir çatlanan patsak planetində tsak taxmağa məcburdur və əksinə, hər bir patsak çatlanan planetində tsak taxmalıdır. (Tsak — burun üçün zəng, həmin planetdə nisbətən aşağı kasta üçün fərqləndirici nişandır). Tsak taxma proseduru hər mənada alçaldıcıdır...
Bu səyahət bürosunun hələ digər planetlərdə nümayəndəlikləri olmadığı üçün daşımalar yalnız Pluk planetindən başqa bir planetə və ya başqa bir planetdən Pluka həyata keçirilir. Uçuşun planlaşdırılması məsələsi sadələşdirilir — planetləri istənilən ardıcıllıqla ziyarət etmək olar (lakin eyni planetə iki dəfə baş çəkmək olmaz — yolda luts tükənə bilər). Elə bir planet ziyarət ardıcıllığı tapmaq lazımdır ki, aralıq planetlərdə tsak taxmaq minimum sayda olsun.
Giriş verilənləri
Girişin ilk sətiri testlərin sayını ehtiva edir. Hər bir testin ilk sətiri N ≤ 22 sayını ehtiva edir — bu uçuşda xidmət göstərilən planetlərin sayı (Pluk planetini saymadan). Növbəti N sətir planetlər haqqında aşağıdakı formada məlumat ehtiva edir: planetin tipi (latın böyük hərfi C — çatlanan, P — patsak), Plukdan bu planetə köçən çatlananların sayı, Plukdan bu planetə köçən patsakların sayı, bu planetdən Pluka köçən çatlananların sayı, bu planetdən Pluka köçən patsakların sayı. Ümumi sərnişin sayı ≤ 1000.
Çıxış verilənləri
Hər bir test üçün çıxış faylında optimal marşrutda neçə dəfə tsak taxılacağını, sonra isə planetlərin ziyarət ardıcıllığını boşluqla ayıraraq yazılır. Giriş faylında sadalanan planetlər birdən başlayaraq nömrələnir, Pluk planetinin nömrəsi sıfırdır və həmişə ardıcıllıqda iki dəfə göstərilir — ardıcıllığın əvvəlində və sonunda. Əgər bir neçə optimal marşrut varsa, daha kiçik nömrəli planetin daha əvvəl ziyarət edildiyi marşrut seçilir.
Nümunəyə şərhlər: birinci uçuşda iki marşrut variantı mümkündür: 0 1 2 0 və 0 2 1 0. Birinci variantda çatlanan planetində 1 beş patsak, öz planetinə 2 tranzitlə gedənlər tsak taxmalı olacaq və növbəti patsak planetində 2, planet 1-də oturan və Pluka gedən beş çatlanan da tsak taxmalı olacaq. Birinci marşrut variantında tsak ümumilikdə 10 dəfə taxılır. 2 variantında aralıq dayanacaqlarda tsak 4 və 1 dəfə taxılır, ümumilikdə 5 dəfə. İkinci variant daha yaxşıdır.
İkinci uçuşda bütün planetlər çatlanan planetləridir, buna görə də tsak yalnız patsaklar tərəfindən taxılacaq. Plukdan patsaklar göndərilmir, lakin üç müxtəlif planetdən bir-bir gəlirlər. İlk ziyarət edilən planet, patsakın pepelatsa minmədiyi yeganə planetdir, sonra isə eyni sərnişin dəstinə malik üç planet gəlir — ikinci addımda qalan üç bərabərhüquqlu planetdən ən kiçik nömrəli planet 2 seçilir, sonra 3 və sonuncu 4. Sonuncu planetdən olan sərnişin aralıq dayanacaqları yoxdur, sondan əvvəlki bir dayanacaq edir və tsak 1 dəfə taxır, qalan sərnişin isə iki aralıq dayanacaqda tsak taxır, ümumilikdə tsak 3 dəfə taxılır.