Description

This problem is partial judge!

We will give you the "inorder" and "preorder" of a tree.

You need to construct a tree by the "inorder" and "preorder" we give you and print the "postorder".

There are three function you need to complete.

Node* buildTree(int *inorder, int *preorder, int *inorder_start, int inorder_end*);

function to construct the tree.

void showPostorder(Node *root)

function to print the postorder

void freeTree(Node *root)

function to free the tree

 

Notice that the the final testcase has small memory limit. If you don't free your tree you will get memory limit exceeded

 

 

 

 

 

(The tree for sample input 1)

(The tree for sample input 2)

Input

 

There are multiple testcases. The testcases will end with EOF.

Each testcase contains three lines.

First line only contains one integer n(1 <= n <= 100) which means the number of nodes in the tree.

Second line contains n integers which in the range of int. Standing for the "inorder".

Third line contains n integers which in the range of int. Standing for the "preorder".

It is guarnteed that no same number will appear in one tree.

Output

For each testcase output the "postorder" of the tree.

You have to output in this form:

testcase<id>: <postorder sequence>

Replace <id> and <postorder sequence> into the i-th testcase and the correct postorder sequence.

Each number in postorder sequence should be followed by a single blank(even the last number).

If you have further questions, please refer to sample output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12390.c

Partial Judge Header

12390.h

Tags

Discuss

Description

 

A famous streamer once said: "I will definitely hit you! I will definitely break your bridge!". The streamer asked you to remember those who annoyed him. They are represented as numbers. When the streamer ask you, you should answer the position of the one the streamer wants to hit.

---

You will got n distinct numbers in increasing order and q for the number of queries.

Suppose the n numbers are stored in an array whose index start from 1.

Each query will give you an integer a_i , then you need to answer the position of a_i in the array.

If you can't find the number in the array, you need to output "Break your bridge!".

example:

6 3 // n = 6, q = 3
4 7 9 20 31 34 // n numbers
4 // answer the position of 4
1 // answer the position of 1
20 // answer the position of 20

In this example you can find "4" in the first place, therefore you should answer "1".

You can't find "1" in the array, therefore you should answer "Break your bridge!".

You can find "20" in the forth place, therefore you should answer "4".

 

You can use the following sample code to solve the problem. It's better you write your own code:

typedef struct _NODE {
	int num, id;
	struct _NODE *left, *right;
} Node;
void build_tree(Node **now, Num *arr, int l, int r) {
	if(l>r) return;
	(*now) = (Node*)malloc(sizeof(Node));
	if(l==r) {
		/*do it your self*/
	}
	else {
		/*do it your self*/
	}
}
int search(Node *now, int x) {
    if(now==NULL) return 0;
	/*do it your self*/
}
void insert(Node **root, int x) {
	/*do it your self*/
}
void freeBST(Node *root){
    if(root == NULL) return;
	/*do it your self*/
}

 

 

Input

Input end with EOF.

Each testcase contains several lines.

First line contains two integer n(1<= n <= 2*10⁶) and q(1<= q<= 2*10⁶)

Second line contains n integer. Each integer range in 1~1000000000

The following are q lines. Each line contains one integer a_i(1<= a_i <= 10⁹)

 

Output

For each query print the position of a_i.

If you can't find a_i in the array, print "Break your bridge!"

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss