Ağacın yuxarısına#5660
Anatoly Cheng McDougal bir çox cəhətdən tipik bir tələbədir. O, mümkün olduqda kodu sıfırdan yazmaq əvəzinə tez-tez kopyalayıb yapışdırmağa çalışır. Bu yanaşma ona daim problemlər yaradır. Məsələn, o, ilk dəfə ikili ağacların preorder, inorder və postorder keçid qaydaları ilə tanış olanda və ona preorder çap edən kod veriləndə, kodu sadəcə kopyalayıb, çap (print) əmrinə doğru yer təyin edib prosedurun adını dəyişdi. Lakin, kodun daxilindəki prosedur çağırışlarının adını dəyişməyi unutdu, nəticədə səhv inorder və postorder çap kodları aldı.
Bu nöqtədə Anatoly tipik tələbə kimi davranmadı. O, əslində kodunu yoxladı! Təəssüf ki, nəticələr düzgün olmayanda o, yenidən tipik tələbə davranışına qayıtdı: panikaya düşdü və hər üç prosedurda çağırış növlərini təsadüfi şəkildə dəyişməyə başladı. Nəticədə vəziyyət daha da pisləşdi.
Anatolinin professoru kodunu təsadüfi simvollardan ibarət bir ağac üzərində yoxladı. O, üç çap prosedurunun nəticəsinə baxanda baş verənləri düzgün təxmin etdi. Lakin, birbaşa kodu yoxlamaq əvəzinə yalnız çıxışa baxaraq Anatolinin kodunu bərpa etməyə qərar verdi. Bunun üçün aşağıdakı düzgün fərziyyələr etdi:
Hər çap prosedurunda çıxış (print) əmri düzgün yerdədir (məsələn, inPrint prosedurunda iki rekursiv çağırış arasında).
Üç prosedur üzrə cəmi altı rekursiv çağırışda dəqiq iki dəfə prePrint, iki dəfə inPrint, iki dəfə postPrint çağırışı istifadə olunur, amma ola bilsin ki, yanlış prosedurlardadır.
Tezliklə professor başa düşdü ki, yalnız çıxışa baxaraq Anatolinin kodunu və test ağacını bərpa etmək asan deyil və nəticə qeyri-müəyyən ola bilər. Siz ona Anatolinin kodunun bütün mümkün bərpasını tapmaqda kömək etməlisiniz. Bundan əlavə, hər bir bərpa üçün təsvir olunan qaydada əlifba sırası ilə birinci preorder çapı olan ağacı tapmalısınız.
Giriş bir testdən ibarətdir. Testdə üç sətr var: Anatolinin prePrint, inPrint və postPrint prosedurlarının çıxışları (müvafiq ardıcıllıqla). Bu sətirlərin hər biri böyük hərfdən ibarətdir (4 \leq n \leq 26), heç bir sətirdə hərf təkrarlanmır. Ən azı bir həllin mövcudluğu zəmanətlidir.
Bütün mümkün bərpaları aşağıda göstərilən qaydada sıralayıb çap edin. Hər bərpa üçün çıxış iki hissədən ibarətdir. Birinci hissə bir sətrdən ibarətdir və Anatolinin prosedurlarındakı altı çağırışı təsvir edir: əvvəlcə iki (rekursiv) prePrint çağırışı, sonra inPrint çağırışları, sonda postPrint çağırışları. Çağırışlar Pre, In, Post sözləri ilə və aralarındakı boşluqla ayrılır. Məsələn, əgər kod düzgün olsaydı, birinci hissədə Pre Pre In In Post Post sətri çap olunardı.
İkinci hissə üç sətirdən ibarətdir və verilmiş çıxışa uyğun gələn ilk ağacı təsvir edir. Birinci sətr ağacın doğru preorder keçidini, ikinci və üçüncü sətirlər isə uyğun olaraq inorder və postorder keçidini göstərir. Əlifba sırasına görə preorder çapı ilk olan ağac alınır. Əgər belə ağaclar bir neçədirsə, aralarında inorder çapı əlifba cəhətdən birinci olanı seçin.
Hər bir bərpa Pre, In, Post seçimlərindən ibarət 6 elementli ardıcıllıqdır. Bərpaların sırası belədir: Pre < In < Post (leksik qaydada).
Nümunə 1