Description

The ternary operator is an operator in C. Its syntax is as follows:

It is often used to replace a simple if-else statement such as:

You can also combine several ternary operators together such as:

Now you are given a ternary expression, in which all the values are either true or false. Next you must evaluate the ternary expression with different combinations of values.

More specifically, a valid ternary expression is either:

or 

And the evaluation order of a ternary expression can be explained as follows:

• If the valid ternary expression is a single value, then just return the value.
• Otherwise:
  • if the value before ? is true then replace this ternary expression as the value of the ternary expression between ? and :
  • if the value before ? is false then replace this ternary expression as the value of the ternary expression after :

Hint: You can apply the idea of a syntax tree to solve this problem.

Input

The first line of the input is a valid ternary expression that contains the ternary operators and value indices.

• It is guaranteed that the value indices are pairwise distinct and range from 1 to the number of values in this ternary expression.
• For example, in the sample input below, the number of values is 5, and the value indices from left to right is 5, 3, 2, 4, 1, respectively.

The next line contains a single integer T, (T <= 5000), representing the number of combinations you have to evaluate.
For the next T lines, each line contains a binary string whose length is equal to the number of values in the ternary expression, giving the setting of each value.

• Note that the i-th character in this binary string (counted from left) is for the value index i. (1 represents true and 0 represents false)
• For string "01101", value indices 1-5 are set as 0,1,1,0,1, respectively.

There are 5 testcases in this problem.
For the first 3 testcases: 1 <= number of values <= 5
For the rest of the testcases: 1 <= number of values <= 3001

Output

For each combination, output the value of the ternary expression. (1 represents true and 0 represents false)
Remember to add a newline character at the end of every line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This is a partial judge problem.  ༼•͟ ͜ •༽

typedef struct _Node {
	struct _Node *left, *right;
	int id;
} Node;

First you have a structure of Node, id represents the index, left and right represents the left node and right node.

Node* buildBinaryTree(int, int*, int*);
void Traversal(Node*, int*);
void freeBinaryTree(Node*); 

You're asked to implement the above three functions.
First, build a binary tree according to the input, next calculate the height of every subtree in one tree traversal. Lastly, free the memory if you ever malloc any.
The height of a node is the number of nodes on the longest simple path from the node to a leaf.
If you think the above description is not clear, you should trace the source code for detailed.
You're highly recommended to create an additional file function.c and compile it with the main source code instead of putting everything in one file.

Note: 
This is a binary patrick star 2.

The following graph is the tree of the first sample input.

Input

The input file contains several testcases (less than 10).
For each testcase, first line contains a single integer N, (1 <= N <= 1000000) represent the number of nodes. The index of nodes is 0 ~ n - 1.
The following N lines each contains two integers represent the left child and right child of the node staring from 0 to n - 1.
If either left child or right child doesn't exist, the value would be -1.
Guarantee the input forms a binary tree and the node 0 is the root.

Output

For each testcase output the height of every subtree starting from 0 to n - 1 seperated by space.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss