Leo cây
Đề bài
Mô tả
Anatoly Cheng McDougal là một sinh viên điển hình theo nhiều nghĩa. Hễ có thể là anh ấy cắt dán mã thay vì tự viết từ đầu. Điều đó chắc chắn gây rắc rối. Chẳng hạn, khi mới học về các phép duyệt cây theo thứ tự trước (preorder), thứ tự giữa (inorder) và thứ tự sau (postorder), anh ấy được cho đoạn mã in cây theo thứ tự trước (bên trái bên dưới), rồi chỉ việc cắt dán đoạn mã đó, chuyển lệnh in đến đúng vị trí và đổi tên thủ tục. Tuy nhiên, anh ấy quên đổi tên các lời gọi thủ tục bên trong, dẫn đến đoạn mã in thứ tự giữa và thứ tự sau bị lỗi như dưới đây.
void prePrint(TNode t) void inPrint(TNode t) void postPrint(TNode t)
{ { {
output(t.value); if (t.left != null) if (t.left != null)
if (t.left != null) prePrint(t.left); prePrint(t.left);
prePrint(t.left); output(t.value); if (t.right != null)
if (t.right != null) if (t.right != null) prePrint(t.right);
prePrint(t.right); prePrint(t.right); output(t.value);
} } }
Đến đây, Anatoly lại không hành xử như một sinh viên điển hình: anh ấy thực sự chạy thử mã của mình! Đáng tiếc, khi kết quả sai, anh ấy quay về đúng kiểu sinh viên điển hình: hoảng loạn và bắt đầu đổi các lời gọi trong cả ba thủ tục một cách ngẫu nhiên, mong sẽ sửa được. Khỏi phải nói, tình hình còn tệ hơn lúc đầu.
Giáo sư của Anatoly chạy thử mã trên một cây ngẫu nhiên gồm các chữ cái. Khi nhìn kết quả in ra của ba thủ tục, bà đoán đúng chuyện đã xảy ra. Tuy nhiên, thay vì xem thẳng mã của anh ấy, bà quyết định thử dựng lại mã của Anatoly chỉ từ kết quả quan sát được. Để làm việc đó, bà đưa ra các giả thiết sau (và các giả thiết này đều đúng):
- Lệnh
outputtrong mỗi thủ tục in nằm đúng vị trí (ví dụ, trong thủ tụcinPrint, nó nằm giữa hai lời gọi đệ quy). - Trong sáu lời gọi đệ quy của ba thủ tục, có đúng hai lời gọi tới
prePrint, đúng hai lời gọi tớiinPrintvà đúng hai lời gọi tớipostPrint, dù có thể chúng nằm sai thủ tục.
Chẳng bao lâu giáo sư nhận ra rằng việc dựng lại mã của Anatoly và cây thử từ kết quả in ra không hề đơn giản, và kết quả có thể không duy nhất. Bạn hãy giúp bà tìm mọi cách dựng lại mã của Anatoly. Ngoài ra, với mỗi cách dựng lại, hãy tìm cây đầu tiên theo thứ tự từ điển (mô tả ở phần dữ liệu ra) cho ra đúng kết quả quan sát được.
Dữ liệu vào
Dữ liệu vào gồm một bộ test duy nhất, gồm ba xâu trên ba dòng: kết quả quan sát được của các thủ tục prePrint, inPrint và postPrint của Anatoly (theo thứ tự đó) trên cùng một cây thử. Mỗi xâu gồm chữ cái in hoa (), không có chữ cái nào lặp lại trong một xâu. Dữ liệu bảo đảm có ít nhất một lời giải.
Dữ liệu ra
In ra mọi cách dựng lại, theo thứ tự mô tả ở đoạn cuối phần này. Mỗi cách dựng lại gồm hai phần.
Phần thứ nhất là một dòng mô tả sáu lời gọi trong các thủ tục của Anatoly: đầu tiên là hai lời gọi (đệ quy) trong thủ tục prePrint của anh ấy, tiếp theo là hai lời gọi trong thủ tục inPrint, cuối cùng là hai lời gọi trong thủ tục postPrint. Các lời gọi được ghi bằng các từ Pre, In và Post, cách nhau bởi dấu cách. Ví dụ, nếu các thủ tục của Anatoly đúng thì phần thứ nhất sẽ là Pre Pre In In Post Post.
Phần thứ hai gồm ba dòng mô tả cây thử đầu tiên có thể sinh ra kết quả quan sát được. Dòng đầu là kết quả duyệt cây theo thứ tự trước đúng, dòng thứ hai và thứ ba lần lượt là kết quả duyệt theo thứ tự giữa và thứ tự sau đúng. Cây đầu tiên là cây có kết quả duyệt thứ tự trước nhỏ nhất theo thứ tự từ điển; nếu có nhiều cây như vậy, cây đầu tiên là cây trong số đó có kết quả duyệt thứ tự giữa nhỏ nhất theo thứ tự từ điển.
Mỗi cách dựng lại là một dãy từ lấy từ Pre, In và Post. Các cách dựng lại được sắp theo thứ tự từ điển của dãy từ, với thứ tự giữa các từ là Pre < In < Post.
Ràng buộc
- .
- Mỗi xâu gồm chữ cái in hoa đôi một khác nhau.
- Có ít nhất một cách dựng lại.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| HFBIGEDCJA BIGEDCJFAH BIGEDCJFAH |
Pre Post In Post In Pre HFBJCDEGIA BIGEDCJFAH IGEDCJBAFH |
Chỉ có một cách dựng lại: prePrint gọi Pre rồi Post, inPrint gọi In rồi Post, postPrint gọi In rồi Pre. |
| BNLFAGHPEDOCMJIK NLBGAPHCODEIJMKF NLFAGHPEDOCMJIKB |
In Pre In Post Post Pre BLNFKMEHAGPCODIJ NLBAGHPEODCMIJKF NLGAPHDOCEJIMKFB Post Pre In In Post Pre BLNFKICPGAHEODMJ NLBGAPHCODEIJMKF NLAGHPDOECJMIKFB |
Có hai cách dựng lại, in theo thứ tự Pre < In < Post của dãy lời gọi; mỗi cách kèm cây có kết quả duyệt thứ tự trước nhỏ nhất. |
Bình luận