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

Partial Judge Header

Discuss

Description

The elephants are queuing in a line. However, some of them are standing in the wrong position, so you are asked to help restore the correct order.

Since the elephants are too lazy to call each other by name, they use a lucky number to recognize one another. Therefore, you will receive a linked list where each node contains a lucky number. Your task is to reverse the order of nodes within the range \([l,r]\) (both inclusive, \(1\)-based).

The I/O functions are already implemented in the given file. You only need to complete the void solve(Node* head, int l, int r) fucntion that returns the same dummy head. Your task is to reverse the linked list within the specified range \([l, r]\).

You can ignore the warning while compiling: cast to smaller integer type 'int' from 'Node *' (aka 'struct Node *') [-Wpointer-to-int-cast]

There is a restriction: You can only modify the “next” pointer of each node to change the order. If you attempt to modify the node values or return a list containing nodes whose addresses do not belong to the original list, you may receive a wrong answer.

Input

The first line contains three integers \(n\), \(l\) and \(r\), representing the size of the list, the start index, and the end index (both inclusive, \(1\)-based).

The second line contains \(n\) integers \(a_1, a_2,...,a_n\), representing the lucky numbers of the elephants.

Contraints

• \(1 \leq l \leq r \leq n \leq 2 \times 10^5\)
• \(1 \leq a_i \leq 10^9\)

Subtask

1. (Testcases 1-2) \(1 \leq l \leq r \leq n \leq 1000\)
2. (Testcases 3-7) No additional Constraints.

Output

Output the modified list of lucky numbers, each followed by a space.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

You are given two rooted binary trees, $X$ and $Y$, in a special format, each with $N$ vertices, numbered from $0$ to $N-1$. The format is described by the following EBNF (Extended Backus–Naur form):

The tree $X$: TREE ::= '(' INT '/' TREE '/' TREE ')' | NIL
The tree $Y$: 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 binary trees are considered identical if and only if:

1. Both trees are empty (NIL), or
2. Both trees have roots, and:
   • Their root values are equal AND
   • Their left subtrees are identical AND
   • Their right subtrees are identical

Here is a example. In the following figure, tree (a) will be represented as (2/(1//)/(0//)) and 2(1()())(0()()),
tree (b) as (2/(0//)/(1//)) and 2(0()())(1()()), and they are NOT identical.

Input

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

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

Contraints

• $1 \leq N \leq 10^5$
• Length of $X$ and $Y$ won't exceed $10^6$
• $X$ only contain character '(', ')', '/' and digit.
• $Y$ only contain character '(', ')' and digit.

Output

If the two trees are identical, output "YES", otherwise output "NO" (without quote)

Noted that you should output one single line.

Sample Input  Download

Sample Output  Download

Discuss

Description

\(N\) people are sitting in a circular hot tub, labeled \(1\) to \(N\) in clockwise order. A scalding wave of bathwater starts at person \(1\) with an initial strength \(K\). The wave travels \(K\) steps circularly. (If \(K\) is positive, the wave moves clockwise; if \(K\) is negative, it moves counter-clockwise).

The person the wave lands on passes out from the extreme heat and is dragged out immediately. Upon their removal, the next wave starts from the person immediately following the fainted individual (in the direction of the previous wave’s travel). The strength of this next wave, \(S\), is equal to the heat tolerance \(T_i\) of the person who just fainted.

This process continues until only one person remains in the tub.

Input

• Line 1: Two integers: \(N\) (the number of people) and \(K\) (the initial wave strength).
• Line 2: \(N\) non-zero integers \(T_1, T_2, \dots, T_N\) representing the heat tolerances of each person

Constraints:

• \(2 \le N \le 10^5\)
• \(-10^9 \le K, T_i \le 10^9\)
• \(K, T_i \neq 0\)

Output

• Line 1: The labels of the people in the order they are removed, each with one space.
• Line 2: The label of the final survivor with '\n'.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

.               

On the left is Katsura, and on the right is Kagura.

Katsura has decided that the group has become far too chaotic. Kagura keeps causing trouble, people keep sending messages to the wrong person, and nobody seems to know who should handle what.

So Katsura creates a new rule called Controlled Centralize.

There are \(n\) members in the group, numbered from \(1\) to \(n\). Member \(1\) is the top leader. Every other member has exactly one direct supervisor.

Under this rule, when two members need to communicate, argue, report an incident, or complain about Kagura eating the emergency snacks again, they are not allowed to deal with it directly. The matter must be passed upward through the chain of command.

The person who handles it is the lowest supervisor who oversees both of them.

You are given the hierarchy of the group. For each communication request, determine who will end up handling the situation.

Hints

For testcases 5-8, you might want to refer to this link's Chapter 18 Tree Queries section for optimization.

Constraints

• \(1 \le n, q \le 2 \times 10^5\)
• \(1 \le a, b \le n\)

Input

Line 1: two integers \(n\), the number of members, and \(q\), the number of requests.

Line 2: \(n - 1\) integers. For each member \(2\) to \(n\), the given integer is their direct supervisor's number.

Each of the next \(q\) lines contains two integers \(a\) and \(b\), meaning members \(a\) and \(b\) need to communicate.

Output

For each request, print the member number who will handle the communication under the Controlled Centralized rule.

Sample Input  Download

Sample Output  Download

Discuss