Description

Calculate the distance between two nodes.

Input

For each case, the first line contains a positive integer N (1 <= N <= 1000), denoting the number of node in the tree (labeled from 1 to N). The second line contains exactly N numbers. The first number denotes the parent of node 1, and the second number denotes the parent of node 2 ..., etc. The parent of the root will be labeled as -1.
Then follows multiple lines of query (query < 10000). Each line contains two positive integers A and B. The query is terminated by two zeros.

Do not assume it is a binary tree.

Output

For each case a line, print the case number first, then output the distance between A and B for each query. Each answer should be separated by a single space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Build a corresponding syntax tree for it.

To parse the infix expression with parentheses, use the grammar below.

EXPR = FACTOR | EXPR OP FACTOR

FACTOR = ID | (EXPR)

EXPR is the expression, ID is one of ‘A’, ‘B’, ’C’, or ‘D’, and OP is one of ‘&’ or ‘|’.

 

You will be provided with main.c and function.h. main.c contains the implementation of functions printPrefix and freeTree. function.h contains the definition of tree node and variables. You only need to implement the following three functions in function.c.

BTNode* makeNode(char c)   // create a node without any child

BTNode* EXPR()   // parse an infix expression and generate a syntax tree

BTNode* FACTOR()   // use the parse grammar FACTOR = ID | (EXPR) to deal with parentheses

 

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The input contains N infix expressions, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. All parentheses are matched. 

Output

The output contains N prefix expressions without parentheses, which are preorders of syntax trees.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10966.c

Partial Judge Header

10966.h

Tags

Discuss

Description

Given an prefix Boolean expression, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Output its infix presentation with necessary parenthesis.

• Ex: input: ||A&BCD
  output: A|(B&C)|D

Hint : About necessary parenthesis, you can observe the syntax tree which has been constructed, then you will find out the rule. For example, the infix expression of |&|AB&CDA with necessary parenthesis is A|B&(C&D)|A, rather than (A|B)&(C&D)|A .

• Syntax tree of |&|AB&CDA

You will be provided with main.c and function.h, and asked to implement function.c.

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The first line will have a number N with the number of test cases, followed by N lines of input, each contain the prefix Boolean expression.

Output

There are N lines infix expression with necessary parenthesis.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10968.c

Partial Judge Header

10968.h

Tags

Discuss

Description

Please create a binary search tree, and support insert operation. Please ignore the repeat number and print out the tree with preorder, inorder and postorder sequence. (The root node is greater than the node in the left subtree and smaller than the node in the right subtree.)

Pre-order:

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

In-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Post-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Input

The input contains two lines. The first line is a integer n (n<=8000) , and the second line is a sequence S, where S contain n non-negative integer number. (The first number in the sequence S is the root.) 

Output

Please print out the tree with preorder, inorder and postorder.(total three line)

Each line has '\n' in the end.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11349.c

Partial Judge Header

11349.h

Tags

Discuss

Description

Give a prefix Boolean expression, which only has at most 26 variables ‘A’, ‘B’, ‘C’... 'Z', and 3 operators, AND ‘&’ , OR ‘|’, and ExclusiveOR '^', print its truth table which output equal to 1.

For example, if input is "4 7 &|AB|CA", then result will be

A B C D

0 1 1 0 
0 1 1 1 
1 0 0 0 
1 0 0 1 
1 0 1 0 
1 0 1 1 
1 1 0 0 
1 1 0 1 
1 1 1 0 
1 1 1 1 

Input

The input contains two unsigned short number (num and length) and a sequences of prefix expression.

• First unsigned short number (num) means the number of variables from 'A' to 'A'+num-1. (e.g. 5 => 'A', 'B', 'C', 'D', 'E' )  1 <= num <= 26
• Second unsigned short number (length) means the length of prefix expression.
• A sequences of prefix expression only has at most 26 variables ‘A’, ‘B’, ‘C’... 'Z', and 3 operators, AND ‘&’ , OR ‘|’, and ExclusiveOR '^'.

Output

Print its truth table which output equal to 1. (It has ' ' behind each number)

Sample Input  Download

Sample Output  Download

Tags

Discuss