K. 나무 위로

Anatoly Cheng McDougal은 여러모로 전형적인 학생이다. 그는 가능하면 코드를 처음부터 작성하는 대신 잘라 붙여 넣으려 한다. 이런 방식은 필연적으로 문제를 일으킨다. 예를 들어 트리의 전위, 중위, 후위 순회를 처음 배우고 트리를 전위 순서로 출력하는 코드(아래 왼쪽)를 받았을 때, 그는 그저 코드를 잘라 붙여 넣은 뒤 출력문을 올바른 위치로 옮기고 프로시저 이름만 바꿨다. 하지만 코드 안의 프로시저 호출 이름을 바꾸는 것을 잊어서, 아래에 보이는 결함 있는 중위 출력과 후위 출력 코드가 만들어졌다. void prePrint(TNode t) { output(t.value); if (t.left != null) prePrint(t.left); if (t.right != null) prePrint(t.right); } void inPrint(TNode t) { if (t.left != null) prePrint(t.left); output(t.value); if (t.right != null) prePrint(t.right); } void postPrint(TNode t) { if (t.left != null) prePrint(t.left); if (t.right != null) prePrint(t.right); output(t.value); } 이 시점에서 Anatoly는 전형적인 학생답지 않게 행동했다. 실제로 코드를 테스트한 것이다! 안타깝게도 결과가 올바르지 않자 그는 다시 전형적인 학생의 행동으로 돌아갔다. 당황해서 세 프로시저의 호출들을 마구잡이로 바꾸기 시작했고, 어떻게든 맞아떨어지기를 바랐다. 말할 것도 없이 상황은 처음보다 더 나빠졌다. Anatoly의 교수는 무작위 문자 트리로 그의 코드를 테스트했다. 그의 세 출력 루틴의 결과를 보고 교수는 무슨 일이 있었는지 정확히 짐작했다. 하지만 그의 코드를 직접 보는 대신, 출력만 관찰해서 Anatoly의 코드를 재구성해 보기로 했다. 이를 위해 교수는 다음을 올바르게 가정했다. 1. 각 출력 루틴의 출력문은 올바른 위치에 있다(예를 들어 inPrint 루틴에서는 두 재귀 호출 사이에 있다). 2. 세 루틴이 수행하는 여섯 개의 재귀 호출 중 정확히 두 개는 prePrint, 정확히 두 개는 inPrint, 정확히 두 개는 postPrint 호출이다. 다만 잘못된 루틴에 들어 있을 수 있다. 곧 교수는 출력만으로 Anatoly의 코드와 테스트 트리를 재구성하는 것이 간단한 일이 아니며 결과가 모호할 수 있음을 깨달았다. 당신이 교수를 도와 Anatoly의 코드의 가능한 모든 재구성(rec\(on- st\)ructions)을 찾아야 한다. 또한 각 재구성마다, 관찰된 출력을 내는 알파벳순으로 가장 앞서는 트리(출력 섹션에 설명된 대로)를 찾아야 한다.

입력은 하나의 테스트 케이스로 이루어져 있다. 테스트 케이스는 세 줄에 걸친 세 문자열, 즉 어떤 테스트 트리에 대한 Anatoly의 prePrint, inPrint, postPrint 루틴의 관찰된 출력(이 순서대로)으로 이루어진다. 각 문자열은 \(n\)개의 대문자(\(4 \le n \le 26\))로 이루어지며, 어떤 문자열에도 반복되는 글자는 없다. 테스트 케이스에는 적어도 하나의 해가 있음이 보장된다.

테스트 케이스의 가능한 모든 재구성을 아래 마지막 문단에 설명된 순서로 출력한다. 각 재구성의 출력은 두 부분으로 이루어진다. 첫 부분은 한 줄로, Anatoly의 루틴들에 있는 여섯 호출을 설명한다. 먼저 Anatoly의 prePrint 루틴의 두 (재귀) 호출, 다음으로 inPrint 루틴의 호출들, 마지막으로 postPrint 루틴의 호출들이다. 호출은 Pre, In, Post라는 단어로 나타내며 공백으로 구분한다. 예를 들어 Anatoly의 루틴이 올바랐다면 재구성 첫 부분의 출력은 Pre Pre In In Post Post가 된다. 둘째 부분은 세 줄로, 관찰된(\(ob- se\)rved) 출력을 만들어 낼 수 있었던 첫 번째 테스트 트리를 설명한다. 첫 줄은 그 트리의 올바른 전위 출력이고, 둘째와 셋째 줄은 각각 올바른 중위와 후위 출력을 담는다(c\(on- ta\)in). 첫 번째 트리란 전위 출력이 알파벳순으로 가장 앞서는 트리이다. 그런 트리가 여러 개면 그중 중위 출력이 알파벳순으로 가장 앞서는 것이 첫 번째이다. 모든 재구성은 Pre, In, Post 중에서 고른 토큰 6개의 나열이다. 재구성들의 순서는 다음 토큰 순서에 대한 사전순이다: P\(re < In < Po\)st.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2013