Ağacın yuxarısına
Anatoliy bir çox cəhətdən tipik bir tələbədir. O, kodu sıfırdan yazmaq əvəzinə, tez-tez kopyalamağa çalışır. Bu yanaşma ona daim problemlər yaradır. Məsələn, ilk dəfə ikili ağacların müxtəlif keçid qaydaları ilə tanış olduqda, post, pre, in və pre-keçid kodunu zirvənin çıxış funksiyasını output çağırışı ilə əldə etdikdə, sadəcə kodu kopyaladı, output çağırışını lazım olan yerə köçürdü və funksiyanı adlandırdı. Lakin keçidlərin bədənindəki funksiyaları adlandırmağı unutdu və yanlış keçid funksiyaları aldı.
Burada Anatoliy özünü tipik tələbə kimi göstərmədi - o, kodunu test etməyə başladı! Təəssüf ki, funksiyaların düzgün işləmədiyini gördükdə, yenidən adi tələbə kimi davranmağa başladı. O, panikaya düşdü və funksiyaların çağırışlarını təsadüfi şəkildə hər üç keçiddə adlandırmağa başladı, ümid edərək ki, onlar düzgün işləməyə başlayacaq.
Anatolinin müəllimi onun kodunu təsadüfi ağaclarda zirvələrdəki simvollarla test edirdi. O, proqramın çıxış məlumatlarına baxdıqda nə baş verdiyini anladı. Bununla belə, kodu yoxlamaq əvəzinə, o, çıxışa əsasən kodu bərpa etməyə çalışdı. Bunun üçün o, ədalətli fərziyyələr etdi:
Simvol çıxış komandası lazımi yerdədir, məsələn, inPrint keçidində funksiyaların çağırışları arasında;
Bütün 6 rekursiv çağırışlar arasında dəqiq iki inPrint, prePrint və postPrint çağırışı, bəlkə də, yanlış yerlərdədir.
Tezliklə müəllim başa düşdü ki, Anatolinin kodunu və test ağacını proqramın çıxışına əsasən bərpa etmək o qədər də asan deyil və nəticə qeyri-müəyyən ola bilər. Siz ona Anatolinin kodunun bütün mümkün bərpalarını tapmaqda kömək etməlisiniz. Üstəlik, hər bir bərpa edilmiş kod üçün proqramın çıxış məlumatlarına görə leksikoqrafik olaraq ən kiçik ağacı tapmaq lazımdır.
Giriş verilənləri
Giriş məlumatları bir testdən ibarətdir, üç sətir - müvafiq olaraq prePrint, inPrint və postPrint funksiyalarının çıxış sətirlərini ehtiva edir. Sətirlər eyni uzunluğa malikdir n (4 ≤ n ≤ 26), hər bir sətirdəki bütün simvollar fərqlidir. Ən azı bir həllin mövcud olduğu təmin edilir.
Çıxış verilənləri
Bütün mümkün bərpaları aşağıda göstərildiyi kimi sıralanmış şəkildə çıxarın. Hər bir bərpa üçün iki hissə çıxarılmalıdır. Birinci hissə bir sətirdən ibarətdir və Anatolinin altı prosedur çağırışını ehtiva edir: ilk iki (rekursiv) prePrint prosedur çağırışı, sonra inPrint prosedur çağırışları və nəhayət postPrint çağırışları. Göstərilən çağırışlar Pre, In və Post sözləri ilə təsvir edilir, boşluqlarla ayrılır. Məsələn, əgər Anatolinin prosedurları düzgün olsaydı, birinci hissə Pre Pre In In Post Post sətirini ehtiva edərdi.
İkinci hissə üç sətirdən ibarətdir və müşahidə olunan çıxışı yarada biləcək ilk test ağacını təsvir edir. Birinci sətir ağacın preorder qaydasında düzgün çıxışını ehtiva edir, ikinci və üçüncü sətirlər isə ağacın müvafiq olaraq inorder və postorder qaydasında düzgün çıxışını ehtiva edir. İlk ağac əlifba sırası ilə ən kiçik preorder çıxışını ehtiva edir. Əgər belə ağaclardan bir neçəsi varsa, onda əlifba sırası ilə ən kiçik inorder çıxışını ehtiva edən ağac çıxarılmalıdır.
Hər bir bərpa Pre, In və Post elementlərindən seçilmiş 6 elementdən ibarət ardıcıllıqdır. Bərpa sırası elementlərin sırasına görə müəyyən edilir: Pre < In < Post.