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

Mr. Kuo is an adventurer. One day, he finds a special "tree".

The tree consists of N vertices. 

There are exactly one simple path between any two vertices.

 

Mr. Kuo wants to do the following operation K times to this tree：

• If the tree is empty, do nothing.
• If the tree consists of one vertex, remove this vertex.
• If the tree consists of two vertices, remove both vertices.
• Otherwise, remove all the leaf of the tree.

（A leaf of a tree is a vertex that is connected to at most one vertex.）

 

Mr. Kuo is wondering how many vertices will remain after he performs the operations K times.

 

Take the sample test as the example：

• In test case 1, {2, 4, 5, 7, 9, 12, 13} are removed and {1, 3, 6, 8, 10, 11} remain.
• In test case 2, {1, 2} are removed and no vertex remains.
• In test case 3, {1, 2, 6, 7} are removed and {3, 4, 5} remain.
• In test case 4, {2, 4, 5} are removed and {1, 3, 6} remain.
• In test case 5, no vertices are removed and {1, 2, 3} remain.

 

The picture below is the tree of the test case 4 in the sample test.

The picture below is the tree after Mr. Kuo performs the operation once.

 

Input

The first line contains one integer T — the number of test cases. Description of the test cases follows.

The first line of each test cases contains two integer N K — the number of vertices in the tree and the number of operations Mr. Kuo performs.

Each of the next N - 1 lines contains two integers u_i and v_i — there is an edge between u_i and v_i.

 

For each test：

1. T ≤ 100, N ≤ 20
2. T ≤ 100, N ≤ 100
3. T ≤ 100, N ≤ 500
4. T ≤ 100, N ≤ 1000
5. T ≤ 100, N ≤ 5000
6. T ≤ 100, N ≤ 20000

1 ≤ u_i, v_i ≤ N

0 ≤ K ≤ N for all test.

Output

For each test case print an integer — the number of verticees remain in the tree.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Bless of Stiff Waist Beast" is a computer virus that will cause the infected computer unable to operate properly. Please help us to calculate the number of infected computers.

The virus is spreading in a network of computers. The network is a tree with $N$ nodes, each node represents a computer. The nodes are numbered from $1$ to $N$ and node $1$ is the root of the tree. Each second, the virus will spread from each infected node to all its children. Initially, only node $1$ is infected. Please calculate the number of infected nodes after $K$ seconds.

• This is a work of fiction. Any resemblance to actual events or persons is entirely coincidental.

Input

The first line contains two integers \(N\) and \(K\), indicating the number of nodes and the number of seconds passed. For the following \(N\) lines:

The \(i\)-th line starts with an integer \(M_i\), indicating the number of children of node \(i\). The following \(M_i\) integers \(c_{i,1}, c_{i,2}, \ldots, c_{i,M_i}\) indicate the children of node \(i\).

\(N \quad K\)
\(M_1 \quad c_{1,1} \quad c_{1,2} \quad \ldots \quad c_{1,M_1}\)
\(M_2 \quad c_{2,1} \quad c_{2,2} \quad \ldots \quad c_{2,M_2}\)
\(\enspace \vdots\)
\(M_N \quad c_{N,1} \quad c_{N,2} \quad \ldots \quad c_{N,M_N}\)

Constraints

\(1 \le N \le 5 \times 10^5\)
\(1 \le K \le 5 \times 10^5\)
\(1 \le M_i \le N-1\)
\(\sum_{i=1}^{N}{M_i} = N-1\)
\(1 \le c_{i,j} \le N\)

Output

Output one integer indicating the number of infected nodes after $K$ seconds.

You should print a newline('\n') character at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Procat has some maps. But some of them are duplicated. He will give you two of them $X$ and $Y$, hoping you could determine whether they are the same or not.

Each map is a rooted tree. The tree consists of $N$ vertices, numbered from $1$ to $N$. There are exactly one simple path between any two vertices.

Procat will give you the map in a special format. The format is described by the following EBNF (Extended Backus–Naur form):

TREE := INT '(' TREE ')' '(' TREE ')' | NIL

It means that a tree is a integer followed by two subtrees or a NIL. The integer represents which vertex the root of the tree is. If the tree is a NIL, it means that the tree is empty.

Two maps are considered the same if and only if they have the same root and for every pair of vertices $(u, v)$ $(1 \le u, v \le N)$, which means the path from $u$ to $v$ in the first map is the same as the path from $u$ to $v$ in the second map.

Let's look at some examples. In the figure below, tree (a) will be represented as 1(2()())(3()()), tree (b) as 1(3()())(2()()), and tree (c) as 3(1(2()())())(). However, only tree (a) and tree (b) are considered the same.

Input

Input contains three lines. The first line contains an integer $N$, the number of vertices in each map.

For the following two lines, each line contains a string, representing map $X$ and $Y$ respectively in the EBNF format.

$N$
$X$
$Y$

Constraints

• $1 \leq N \leq 10^5$
• length of $X$ and $Y$ won't exceed $10^6$ characters
• $X$ and $Y$ only contains characters '(', ')' and digits.

Output

If the two maps are the same, output "YES". Otherwise, output "NO".

Noted that you should output only one single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem, you are asked to implement the quick sort algorithm. The quick sort algorithm is a divide and conquer algorithm that works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

• This is a partial judge problem. Input and output are handled by 14216.c. All you have to do is implement two functions pickPivot and rearrange.
• int* pickPivot(int* begin, int* end);
  This function should return a pointer to the pivot element. Notice that the pivot element should be in the array. How you choose the pivot will affect the performance of the quick sort algorithm. You should choose the pivot such that the array is divided into two sub-arrays of approximately equal size.
• int* rearrange(int* begin, int* end, int* pivot);
  This function should rearrange the elements in [begin, end) such that all elements less than to the pivot are to the left of the pivot, and all elements greater than the pivot are to the right of the pivot. The function should return a pointer to the pivot element after rearranging.

Input

The input consists of two lines. The first line contains an integer \(N\), the number of elements in the array. The second line contains \(N\) integers \(a_1, a_2, \cdots, a_N\), the elements of the array.

\(N\)
\(a_1 \quad a_2 \quad \cdots \quad a_N\)

Constraints

• \(1 \leq N \leq 10^5\)
• \(-10^9 \leq a_i \leq 10^9\)

Output

The output should contain one lines with \(N\) integers, the elements of the array after sorting. There should be a space after each integer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14216.c

Partial Judge Header

14216.h

Tags

Discuss