Woburn Challenge 2001
Problem 2: The Island of Dr. Strangelove
There’s a problem. After following his map to what should have been the Okagor camp, Mason realizes that the mission will fail, for he has landed on Temptation Island, not Survivor Island. Since John Patrick Mason bears a passing resemblance to Sean Connery, he is quickly surrounded by a bevy of women who are quite forthcoming with their phone numbers. Pulling out his standard issue SAS black book, Mason quickly jots down the numbers he is being given. But what if he is captured by the men’s camp…who knows what havoc would be wreaked if the phone numbers fell into their hands. As a result, he encrypts the number using a simple method that reckons back to his computer science days at Seton Hall. He considers the digits of the phone number to represent the postfix traversal of a binary search tree (see next page for an explanation of binary search trees). He encrypts them by writing down the prefix traversal of the same tree. Later that evening, someone in the men’s camp steals Mason’s black book and tries to decrypt the information. Immediately recognizing the code as a post-to-prefix encryption he sets about decrypting the phone numbers.
Each phone number is a series of positive integers no greater than 32767 (each “digit” is an integer) and no phone number contains any duplicate digits.
Your job is to decrypt a series of numbers (convert them back from prefix to postfix). Although it is guaranteed that the digits are distinct, for some inputs a search tree with the desired prefix traversal cannot be formed. If so, print out
No such tree; otherwise, print out the decryption, i.e. the postfix traversal of the same tree. Note that with the installation of new area codes, the phone numbers can be up to 500 “digits” long.
InputThe first line of the input contains T, the number of test cases.Each of the T remaining lines of the input will contain a phone number encoded using Mason’s post-to-prefix method: the first digit on the line is N, the number of digits in the phone number (1 ≤ N ≤ 500) and following that is the encoded phone number itself.
For each input, output either the decoded phone number, or
No such tree.
7 4 2 1 3 6 5 7
8 6 2 1 4 8 9 11 10
5 9 7 12 5 11
1 3 2 5 7 6 4
1 4 2 10 11 9 8 6
No such tree
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 23, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3