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

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

Partial Judge Header

Tags

Discuss

Description

Niflheimr discovers an interesting fact: trees grow upward in real world, but trees grow downward in CS world.
He decides to study the trees in CS world, so he choose the simplest one for his study: binary tree. Before study begins, he needs to construct a binary tree first.

Given a in-order traversal sequence and a pre-order traversal sequence of a binary tree, construct the binary tree and print the post-order traversal sequence of that binary tree.

Hint:

      1. If you have no idea how to implement, please take it as your reference.

function.h

#include <stdlib.h>
#include <stdio.h>
typedef struct _node {
    int value;
    struct _node *left;
    struct _node *right;
} Node;

Node *create_node(int value);
void postorder(Node *root);
void destroy(Node* root);

/*
    Parameter description:
    int *inorder : the inorder traversal sequence of the binary tree.
    int *preorder : the preorder traversal sequence of the binary tree.
    int inorder_start : the starting index of the inorder traversal of the subtree.
    int inroder_end : the ending index of the inorder traversal of the subtree.

    As for the preorder traversal index, try declaring a static variable inside this function.
*/
Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end);

      2. If you get a TLE in the last testcase, try to think over the property underlined in "Input" section.

​

Input

 The first line of input contains a integer N, indicating the number of nodes on the tree.
The second line contains N distinct numbers, which is the in-order traversal sequence of the binary tree.
The third line contains N distinct numbers, which is the pre-order traversal sequence of the binary tree.

It is guaranteed that:

• 1 ≤ N ≤ 2*10⁵
• For all x being the number on the binary tree, 0 ≤ x ≤ N-1.

Output

Print out the post-order traversal sequence of the binary tree.
There is a white space after each number (including the last one). For example, [0 1 2 3 ].
Remember to print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Give a prefix Boolean expression, which only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’, print its truth table.

For example, if input is "|&AC|AB", then result will be

A B C D output

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

Input

The input contains a sequences of prefix expression. It only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’. The length of prefix expression is shorter than 30.

Output

It has 5 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. Lu is a famous magician. There’s a poker magic tutorial on his youtube channel.
There’re N stacks of cards on the table at begining.
And then, Mr. Lu make M actions on these card stacks.
There’s only two kinds of actions Merge and Cut:

• Merge x y: put the x-th card stack on the top of y-th card stack.
• Cut x i: cut the x-th card stack into two stacks. One is the card stack contains ( 1~i )-th cards of original stack. The other one is the remaining. The former’s index will be x, the latter’s will be (x+1)
• The indexes of stacks and cards will be changed after Merge and Cut.

For example:

As a lazy CS student, you only focus on the result.
Therefore, you decide to write a program to compute the final state of card stacks.

It’s partial judge for this problem.
Please download the code at the bottom to see the interface and main function.
You have to implement a data structure like below:

Input

Two integer N,M on the first line.
For each of the next N lines, there’re several integers Ni and Ci,1,Ci,2...Ci,Ni.
Ni means the number of cards in the i-th stack.
Ci,j denotes the j-th card of i-th stack.

The folloing M lines contains one action per line.
Every Action is one of “Merge x y” or “Cut x i”.

It’s guaranteed that:

• 1 ≤ N, M ≤ 9000
• ∑ Ni ≤ 4∗10⁴
• Ci,j is non-negative integer.
• In “Merge x y” action:
  • the x, y-th stacks always exist.
  • x is not equal to y.
• In “Cut x i” action:
  • the x-th stack always exists.
  • i is always between 1 and Nx - 1.
• There’s at least 1 card in each card stack.

Output

Print the card stacks by the order of index.
One line for one card stack.

Please refer to the sample input/output for the precise format.
There is a ‘\n’ at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

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

Today is your birthday, your father wants to prepare a gift for you. He ranks his brains and finally decide what to give. Since you are a college student major in computer science, he gives you a rooted binary tree for your birthday! But at the time you are unpacking the gift, you accidentally damage the binary tree! What a pity! You have tried very hard to restore the information of the binary tree but end up failure. For each node, you know which two nodes are its children, but you don't know which one is left child and which one is right child.

Fortunately, There's an inorder traversal sequence of the binary tree on the package, and you want to know whether the broken information of the binary tree is possible to form the inorder traversal sequence on the package.

Note:

The following figure is the way to form the tree that meets the input of sample testcase 1 and its inorder traversal is identical to the input inorder traversal.

Input

The input contains T testcases.

The first line of each testcase contains a single integer N representing the number of node in the binary tree. The index of nodes in the binary tree is 1-based. 

For the following N lines, each line contains two integers. For i-th line, the two integers represent the children of i-th node. 0 represents that the node doesn't exist.

Next line of the input contains N integers representing the inorder traversal sequence.

Constraint of testcases:

Testcase 1: N <= 5, T <= 4.
Testcase 2: T = 20, N <= 15, and node 1 is guarantee to be the root of the binary tree.
Testcase 3: T = 20, N <= 2000, and node 1 is guarantee to be the root of the binary tree.
Testcase 4: N * T <= 4 * 10⁶, N <= 2 * 10⁵, and node 1 is guarantee to be the root of the binary tree.
Testcase 5: T = 20, N <= 15.
Testcase 6: T = 20, N <= 2000.
Testcaes 7: T = 20000, N <= 10.
Testcase 8 ~ 10: N * T <= 4 * 10⁶, N <= 2 * 10⁵.

Output

For each testcase, if there exists a way to distribute nodes to left child or right child that its inorder traversal is identical to the input inorder traversal, then output "YES" otherwise "NO".

Remember to add a newline character at the end of every line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

What is a Perfect Binary Tree?

A perfect binary tree is a binary tree data structure with the following characteristics:

• Every level of the tree is completely filled with nodes. In other words, each level has the maximum number of nodes possible for that level.
• Each node in the tree has either two children or no children, and a node that has no children makes it a leaf node.
• The total number of nodes in a perfect binary tree of height h is 2^h+1 - 1. (Note that the height of the following example tree is 2 not 3.)

What is a Binary Search Tree?

A binary search tree (BST) is a binary tree data structure with the following properties:

• Each node in the tree has at most two child nodes (binary tree).
• For any node, its value is greater than or equal to the values stored in the left subtree.
• For any node, its value is smaller than the values stored in the right subtree.
• For any node, the left subtree and the right subtree are binary search trees respectively as well.

We know that the preorder traversal is based on the order "root -> left subtree -> right subtree". Therefore, for the preorder traversal sequence of a binary search tree, we can observe that the first number is the root of the tree, and in the following sequence, numbers smaller than or equal to the root belong to the left subtree (green part), while numbers larger than the root belong to the right subtree (blue part).

In this problem:

You are given the preorder sequence of a scrambled perfect binary search tree with unique node values, where the left and right subtrees of several nodes of the original tree have been swapped. See the following example of swapping node 8's and then node 12's left and right subtrees.

Can you help us reconstruct the original binary search tree and output its postorder sequence?

Input

• The first line contains an integer N  (1 ≤ N ≤ 10⁵) - the length of the preorder sequence for the scrambled perfect binary search tree.
• The second line contains N integers x₁, x₂, ..., x_N (1 ≤ x_i ≤ 10⁹) - representing the preorder sequence.

Output

Output one line that contains N integers - representing the postorder sequence of the original perfect binary search tree. Remember to print '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Big Orange Cat (大橘) found a strange orange tree in his backyard, represented as a syntax tree with n nodes. Each node is either a number or an operator, including basic operators (+, -, *) and m custom operators.

Each custom operator (the i-th one) is defined as follows:

• o_i: the symbol representing the operator.
• k_i: the number of input parameters (child nodes) it accepts.
• s_i: the preorder traversal of the syntax tree defining its computation rule, consisting only of +, -, *, and numbers.

In the syntax tree, parameters are denoted as A (first parameter), B (second parameter), and so forth. For example:

The custom operator @(A, B) computes (A + B) * (A - B), represented by the preorder traversal * + A B - A B.

Given the expression @ 10 13, where A = 10 and B = 13, it expands to * + 10 13 - 10 13, calculating as (10 + 13) * (10 - 13) = 23 * (-3) = -69.

The syntax tree can be visualized as:

• The expanded form of @ (top).
• The tree with A = 10 and B = 13 substituted (bottom).

Input

The first line contains three integers: n, m, and q, which represent the total number of nodes, the number of custom operators, and the number of operations, respectively.

The next m lines describe the custom operators. Each line includes:

• A character o_i: the symbol of the i-th custom operator.
• A positive integer k_i: the number of input parameters it takes.
• A string s_i: the preorder traversal result of the syntax tree created by this operator’s rule, made up of numbers and operators (including +, -, *), with each operator or number separated by a space.

Next line contains a string representing the syntax tree’s preorder traversal result, with each element separated by a space.

The following q lines represent q operations, where each operation can be one of these:

• 1 index symbol: Change the symbol of the node at position index to symbol.
• 2 index num: Change the number of the node at position index to num.
• 3 index1 index2: Swap the subtrees of the nodes at positions index1 and index2.
• 4: Output the result of the current syntax tree after calculation, modulo 10⁹ + 7.
   

Constraints

• 1 <= n <= 10⁴
• 0 <= m <= 10
• 1 <= q <= 10⁵
• t and s_i are made up of numbers and visible characters, and s_i will not contain other custom operators.
• 1 <= | s_i | <= 150
• o_i will be a visible character other than +, -, or *
• All numbers are between [0, 10⁹].
• k_i = 2
• The number of type 4 operations (output results) is <= 100.

Subtasks

Output

Whenever the operation 4 is encountered, output the result of the current syntax tree after calculation, modulo 10⁹ + 7. If the result after applying 10⁹ + 7 is negative, add 10⁹ + 7 to it before outputting. You can refer to Example 2: the original calculation result is -69, and after adding $10^9 + 7$, it becomes 999999938.

Explanation of Sample Test Case 3:

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

INTP is not MBTI, but the task you need to perform: INsert The Parentheses tree.

You are given a binary search tree of length N represented in parentheses. The binary search tree is represented according to the following rule:

If a node is NULL, represent it as ()

Next, you will perform T insertion operations. Each operation involves inserting a node with value A. The insertion rule is as follows:

Starting from the root node, if A is less than the current node's value, move to the left subtree. If A is greater than the current node's value, move to the right subtree, until an NULL node is found. Insert a node with the value A at that NULL node.

Finally, output the binary tree after completing the operations, expressed in parentheses.

For sample input:
3(2(1()())())(4()())

The Parentheses tree is guaranteed to satisfy the following condition before and after all T operations:

• As a binary search tree, it ensures each node's left child is less than the node and its right child is greater.
• All node values in the tree are unique.

This question is a partial judge.
Please implement functions defined in the header file.

• parenthesesTree: Construct a parentheses tree based on a given parentheses expression.
• insert: Insert a node with value A into the parentheses tree.
• print: After all insertion operations are complete, output the parentheses tree as a parentheses expression.

Input

The first line contains an integer N, representing the length of the string expression of the parentheses tree.
The second line contains a parentheses expression of length N.
The third line contains an integer T, representing the number of insertion operations to perform.
The following T lines each contain an integer A, representing the value of the node to be inserted into the binary tree.

Constraints

• 0 ≤ N ≤ 10⁶
• 1 ≤ T ≤ 100
• -10⁹ ≤ D, A ≤ 10^9​

Subtask

• Testcases 1 ~ 3: T = 0
• Testcases 4 ~ 6: No additional restrictions

Output

Output the binary tree after completing the operations, expressed in parentheses.

Please remember to print "\n" at the end.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss