{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAnatoly Cheng McDougal là một học sinh điển hình ở nhiều mặt. Khi có thể, anh ấy cố gắng cắt và dán mã thay vì viết từ đầu. Không tránh khỏi, cách tiếp cận này gây ra vấn đề cho anh ấy. Ví dụ, khi anh ấy lần đầu tiên học về các cách duyệt cây theo thứ tự trước, theo thứ tự giữa và theo thứ tự sau, và được cung cấp mã cho việc in thứ tự trước của một cây (hiển thị bên trái dưới đây), anh ấy đơn giản là cắt và dán mã, sau đó di chuyển lệnh in đến vị trí đúng và đổi tên thủ tục. Tuy nhiên, anh ấy quên đổi tên các cuộc gọi thủ tục bên trong mã, dẫn đến mã in thứ tự giữa và mã in thứ tự sau bị lỗi như dưới đây.\u003c/p\u003e\n\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; border-bottom-color:black; text-align:left\"\u003e\n \u003cpre\u003e\u003csmall class\u003d\"small\"\u003evoid prePrint(TNode t)\n{ \n output(t.value);\n if (t.left !\u003d null)\n prePrint(t.left);\n if (t.right !\u003d null) \n prePrint(t.right);\n}\n\u003c/small\u003e\n\u003c/pre\u003e\n \u003c/td\u003e\n\n \u003ctd style\u003d\"border-top-style:solid; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:left\"\u003e\n \u003cpre\u003e\u003csmall class\u003d\"small\"\u003evoid inPrint(TNode t)\n{\n if (t.left !\u003d null)\n prePrint(t.left);\n output(t.value);\n if (t.right !\u003d null)\n prePrint(t.right);\n}\n\u003c/small\u003e\n\u003c/pre\u003e\n \u003c/td\u003e\n\n \u003ctd style\u003d\"border-top-style:solid; border-bottom-style:solid; border-bottom-width:1px; border-bottom-color:black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:left\"\u003e\n \u003cpre\u003e\u003csmall class\u003d\"small\"\u003evoid postPrint(TNode t)\n{\n if (t.left !\u003d null)\n prePrint(t.left);\n if (t.right !\u003d null)\n prePrint(t.right);\n output(t.value);\n}\n\u003c/small\u003e\n\u003c/pre\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003c/center\u003e\n\n \u003cp\u003eTại thời điểm này, Anatoly không còn cư xử như một học sinh điển hình nữa. Anh ấy thực sự kiểm tra mã của mình! Thật không may, khi kết quả không chính xác, anh ấy quay trở lại cách cư xử của học sinh điển hình. Anh ấy hoảng sợ và bắt đầu thay đổi ngẫu nhiên các cuộc gọi trong tất cả ba thủ tục, hy vọng sẽ làm đúng mọi thứ. Không cần phải nói, tình hình trở nên tồi tệ hơn bây giờ so với khi anh ấy bắt đầu.\u003c/p\u003e\n\n \u003cp\u003eGiáo sư của Anatoly đã kiểm tra mã trên một cây ký tự ngẫu nhiên. Khi bà nhìn vào kết quả của ba thủ tục in, bà đoán đúng những gì đã xảy ra. Tuy nhiên, thay vì đi trực tiếp đến mã của anh ấy, bà quyết định thử tái tạo mã của Anatoly chỉ bằng cách quan sát kết quả. Để làm điều này, bà đưa ra những giả định đúng như sau:\u003c/p\u003e\n\n \u003col class\u003d\"enumerate\"\u003e\n \u003cli\u003e\n \u003cp\u003eLệnh in trong mỗi thủ tục in đúng vị trí (ví dụ, giữa hai cuộc gọi đệ quy trong thủ tục \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e).\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eTrong sáu cuộc gọi đệ quy được thực hiện bởi ba thủ tục, chính xác hai cuộc gọi đến \u003ctt class\u003d\"ttfamily\"\u003eprePrint\u003c/tt\u003e, chính xác hai cuộc gọi đến \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e, và chính xác hai cuộc gọi đến \u003ctt class\u003d\"ttfamily\"\u003epostPrint\u003c/tt\u003e, mặc dù có thể ở trong các thủ tục sai.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ol\u003e\n\n \u003cp\u003eSớm giáo sư nhận ra rằng việc tái tạo mã của Anatoly và cây thử nghiệm từ kết quả của anh ấy không phải là một nhiệm vụ đơn giản và kết quả có thể mơ hồ. Bạn sẽ phải giúp bà tìm tất cả các tái tạo có thể của mã của Anatoly. Ngoài ra, đối với mỗi tái tạo như vậy, bạn phải tìm cây có thứ tự trước theo thứ tự chữ cái (như mô tả trong phần kết quả) tạo ra kết quả quan sát được.\u003c/p\u003e\n\n \u003ch2\u003eNhập\u003c/h2\u003e\n\n \u003cp\u003eĐầu vào bao gồm một trường hợp kiểm tra duy nhất. Một trường hợp kiểm tra bao gồm ba chuỗi trên ba dòng riêng biệt: kết quả quan sát được của thủ tục \u003ctt class\u003d\"ttfamily\"\u003eprePrint\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e và \u003ctt class\u003d\"ttfamily\"\u003epostPrint\u003c/tt\u003e của Anatoly (theo thứ tự đó) trên một số cây thử nghiệm nào đó. Mỗi chuỗi này bao gồm \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e chữ cái in hoa (\u003cspan class\u003d\"tex2jax_process\"\u003e$4 \\le n \\le 26$\u003c/span\u003e), không có chữ cái lặp lại trong bất kỳ chuỗi nào. Trường hợp kiểm tra được đảm bảo có ít nhất một giải pháp.\u003c/p\u003e\n\n \u003ch2\u003eKết quả\u003c/h2\u003e\n\n \u003cp\u003eHiển thị tất cả các tái tạo có thể cho trường hợp kiểm tra, được sắp xếp như mô tả trong đoạn văn cuối cùng dưới đây. Kết quả cho mỗi tái tạo bao gồm hai phần. Phần đầu tiên là một dòng duy nhất và mô tả sáu cuộc gọi trong các thủ tục của Anatoly: trước tiên là hai cuộc gọi (đệ quy) trong thủ tục \u003ctt class\u003d\"ttfamily\"\u003eprePrint\u003c/tt\u003e, tiếp theo là các cuộc gọi trong thủ tục \u003ctt class\u003d\"ttfamily\"\u003einPrint\u003c/tt\u003e của anh ấy, và cuối cùng là các cuộc gọi trong thủ tục \u003ctt class\u003d\"ttfamily\"\u003epostPrint\u003c/tt\u003e của anh ấy. Các cuộc gọi được mô tả bằng từ \u003ctt class\u003d\"ttfamily\"\u003ePre\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eIn\u003c/tt\u003e, và \u003ctt class\u003d\"ttfamily\"\u003ePost\u003c/tt\u003e, cách nhau bằng khoảng trắng. Ví dụ, nếu các thủ tục của Anatoly đúng, kết quả của phần đầu tiên của tái tạo sẽ là \u003ctt class\u003d\"ttfamily\"\u003ePre Pre In In Post Post\u003c/tt\u003e.\u003c/p\u003e\n\n \u003cp\u003ePhần thứ hai bao gồm ba dòng và mô tả cây thử nghiệm đầu tiên có thể tạo ra kết quả quan sát được. Dòng đầu tiên là thứ tự trước đúng của cây, và hai dòng tiếp theo chứa thứ tự giữa đúng và thứ tự sau đúng, tương ứng. Cây đầu tiên là cây có thứ tự trước đúng theo thứ tự chữ cái. Nếu có nhiều cây như vậy, cây đầu tiên trong số đó là cây có thứ tự giữa đúng theo thứ tự chữ cái.\u003c/p\u003e\n\n \u003cp\u003eMỗi tái tạo là một chuỗi 6 token được chọn từ \u003ctt class\u003d\"ttfamily\"\u003ePre\u003c/tt\u003e, \u003ctt class\u003d\"ttfamily\"\u003eIn\u003c/tt\u003e, và \u003ctt class\u003d\"ttfamily\"\u003ePost\u003c/tt\u003e. Thứ tự của các tái tạo được sắp xếp theo thứ tự từ điển theo thứ tự của các token: \u003ctt class\u003d\"ttfamily\"\u003ePre \u0026lt; In \u0026lt; Post\u003c/tt\u003e.\u003c/p\u003e\n\n \u003ch2\u003eVí dụ 1\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eHFBIGEDCJA\nBIGEDCJFAH\nBIGEDCJFAH\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ePre Post In Post In Pre\nHFBJCDEGIA\nBIGEDCJFAH\nIGEDCJBAFH\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n \u003ch2\u003eVí dụ 2\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eBNLFAGHPEDOCMJIK\nNLBGAPHCODEIJMKF\nNLFAGHPEDOCMJIKB\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eIn Pre In Post Post Pre\nBLNFKMEHAGPCODIJ\nNLBAGHPEODCMIJKF\nNLGAPHDOCEJIMKFB\n\nPost Pre In In Post Pre\nBLNFKICPGAHEODMJ\nNLBGAPHCODEIJMKF\nNLAGHPDOECJMIKFB\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}