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

Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Please remove unnecessary parentheses and print the infix expression. Existence of unnecessary parentheses doesn’t affect the result of expression. For example,

(A&B)|(C&D) → A&B|(C&D)

(((A|B))) → A|B

Hint: You can combine two homework. Build a syntax tree and print the infix expression with necessary parentheses.

For OJ submission:

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

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

Input

The input is an infix expression, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. The length of the infix expression is less than 256.

Output

The output is an infix expression without unnecessary parentheses.

Sample Input  Download

Sample Output  Download

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

In this problem, you are given a prefix Boolean expression, which has at most N=10^5 variables and 2 kinds of operators ‘&’ and ‘|’. Each variable has an ID number. The values of these variables can be either 0 or 1, and are all initialized as 0.

You will be given M ID numbers. For each ID number, you should flip (0 will become 1, 1 will become 0) the value of the corresponding variable and then compute/output the result of the prefix Boolean expression.

Example:

Assume the prefix Boolean expression is &[1][2] and the given ID numbers are “2 1”. First the value of variable 2 will change from 0 to 1. The output of &[1][2] is 0&1=0. Next, the value of variable 1 will change from 0 to 1. The output of &[1][2] is 1&1=1.

Hint: (You can go to the Input/Output description directly, and come back for hints if necessary.)

Hint 1: To solve this problem, you can parse the input and derive the output recursively each time a variable is flipped. Unfortunately, this brute-force approach is not efficient and can lead to TLE, in particular the 3^rd and 4^th testcases in this problem. We encourage you to use the syntax tree of the prefix Boolean expression for better efficiency.

Hint 2: The key idea behind the syntax-tree approach is to avoid re-evaluation of the whole expression every time a bit is flipped. Some more hints are provided for you as follows:

• [Data structure] Use a tree node pointer array to record the address of each variable (leaf) node of the syntax tree: you can locate each variable to be flipped directly;
• [Data structure] For each tree node i, record the value of its subtree (rooted at node i);
• [Algorithm] Starting from the variable node to be flipped, move upward following the syntax tree and update the node values until the output of the syntax tree (or the Boolean expression) can be determined. 

Example:

Consider the following syntax tree for "|&|[1][2][3][4]". Assume [1] is flipped. You will find that the value of node A should be changed to 1|0=1. Moreover, you note that the value of B remains unchanged, i.e., 1&0=0, and the checking process can stop.

Later, when [3] is flipped, both the values of node B and the root node should be changed. In this case, the output is also changed.

Sample structure:

typedef struct node{

    int value; // This is the value of the subtree, not the ID number

    int tokentype;

    struct node *leftchild;

    struct node *rightchild;

    struct node *parent; //pointing to the parent node

}Node;

Node* variable[100001]; // This array stores the pointers pointing to the tree nodes. For example, variable[0] points to the node with ID number 0.

Input

The first line has one number T, 0<T<= 7, indicating the number of testcases.

The following lines are the inputs of the testcases.

Each testcase contains three lines:

1. N, M (0<N<=100000, indicating the number of variables in a given prefix Boolean expression. 0<M<=100000, indicating how many times the values are flipped).

2. A string S, describing the prefix Boolean expression (& means and gate, | means or gate, [i] means a variable ID)

3. M numbers, where each number i means the value of variable i is flipped. The order matters.

Note that all the variables are initially 0.

Each ID number only appears once in the prefix Boolean expression.

The depth of the tree is no more than 30.

Output

For each testcase, you should output M lines, each showing the output of the prefix Boolean expression after a variable is flipped.

0 for false, 1 for true.

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

Niflheimr is a poor student. He can’t afford to buy a scientific caculator, but his simple calculator can’t type in a mathematical expression.

So he decided to create a calculator on his own!
He learned in class that he can evaluate an expression by converting the expression into prefix and create a binary tree accordingly.

Unfortunately, Niflheimr is a careless and thrifty person.
He often types the expression wrong, and if that happens, after he removed the wrong part, he has to rebuild the whole binary tree and calculate everything again.
Furthermore, Niflheimr likes to reuses the same expression many times because a expression may have several sub-expressions (i.e. *-43+21 contains +21, -43, *-43+21).
He thinks that rebuilding is too sloooooooooow, so he asks you to help him make it fast.
If you can help him correctly, he will feel happy and give you a big AC.

Hint: If you got a TLE, instead of rebuilding the tree all the time, try to add some extra field in the node inside the binary tree, e.g. size, and utilize them to speed up operations.

For example, you can define your Node inside the binary tree like this:

typedef struct _node {
    int dark_magic; // ???
    int size; // ??? Use this field to find the index of each node. Try figure out HOW TO by yourself!
    int type; // which kind of operation is this node, e.g. NUM / ADD / SUB / MUL.
    struct _node *left, *right, *parent;
} Node;

-------------------- 2020/04/13 16:40 Important Update --------------------
Because of the property of % operator, there will be 2 kind of answer for each output.
For example, 10006 mathematically equals to -1 under module 10007, while 10006 is not equal to -1 under % operation
( 10006%10007 = 10006, -1%10007 = -1).
To avoid this situation, Please revise each result r into the output x which satisfies:

• r mathematically equals to x under module 10007.
• 0 ≤ x < 10007

Ex: -1, -10 should be revised into 10006, 9997 respectively.

Input

First line of input is an integer N, indicating the # of operations.
Second line of input is the expression in prefix. The expression contains only +, -, * and digits. All the number in the expression are between 1 and 9, that is, every number in the expression are DIGITS(個位數).

There’s one kind of operations on the each of following N lines.
Type of operations:

• “D A B”: delete from A-th character to B-th character in the expression.
• “Q A”: print the value of sub-expression with root at A-th character in the expression.

Note that the index starts from 1, and the index of the characters in the expression should be re-calculated after each deletion.

It is guaranteed that:

• The length of the expression is less than 3∗10⁵
• 1 ≤ N ≤ 10⁵
• The height of the binary tree is always ≤ 20.
• 1 ≤ A, B ≤ length of expression
• The expression is always valid after each operation “D A B”.
• The expression will never be empty.
• There won’t be any cross-subtree deletion, i.e. the following case won’t happen in our testcase:
  

Output

Print the value of sub-expression for each operation “Q A”.
Niflheimr hates negative and big numbers, since it will make calculation more complex. So for every output, please print the result after modulo 10007, which means the output is between 0~10006.

Explantation of Sample IO

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This problem uses partial judge. Please select gcc compiler when submitting.

A binary search tree is a binary tree that has the following properties:

1. For any node, its key is greater than the keys stored in the left subtree.

2. For any node, its key is smaller than the keys stored in the right subtree.

3. For any node, the left subtree and the right subtree are binary search trees respectively as well.

4. Every node has a unique key. No two nodes share the same key.

For example, the two following trees are binary search trees.

Given the pre-order traversal of a binary search tree, please output the in-order traversal and post-order traversal of the binary search tree. It can be proven that for no two binary search tree shares the same pre-order traversal.

Input

The first line is an integer T, meaning that there are T test cases in a single input file.

For each test case, the first line is an integer N, denoting the size of the binary search tree. The next line are N integers, denoting the pre-order traversal of the binary search tree.

• 1 <= T <= 2000

• 1 <= N <= 106

• 1 <= N x T <= 2 x 106

  • Be careful of memory leak

  • To pass all test cases, try to come up with an O(N) algorithm to build the binary search tree.

• 0 <= key of node <= 109

Output

For each test case, please output two lines: The first line is the in-order traversal of the binary search tree. The second line is the post-order traversal of the binary search tree.

Note that there is a space after each output number. e.g. use printf("%d ", var_to_be_printed) when printing.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

There is a growing Binary Search Tree(gBST) in Hakka's village,
the gBST is original a binary search tree,
a binary search tree is rooted binary tree,
the value stored in each node is greater than any value stored in the left subtree,
and less than any value stored in the right subtree.

One night, the Hakka's found that the gBST growed larger,
some random values are added into the gBST, in random position.

In order to make gBST maintain a Binary Search Tree,
the Hakka's need to prune the tree.
And since Hakka's are frugal, they want the gBST to have as many nodes as possible.

To prune a node off the gBST, this node must be a leaf of the gBST,
a leaf of the tree is a node with no left subtree and no right subtree.
Every round of pruning, the Hakka's will prune all leaves that need to be removed,
until the gBST turns back to a binary search tree.

So before the pruning process start,
the Hakka's ask you to mark the node to 'negative X' if the node will be pruned at round X.
If the node will remain on the gBST, you don't need to mark the node.

ouo.

For Sample Input 1,
7
5 1 9 2 4 6 11
0 1L 1R 2L 3L 5L 3R

 

Input

Input contains 3 lines.

The first line contains an integer N, represent the number of nodes after gBST grows.

The second line contains N numbers Vi, represents the value stored on the node with index i.

The third line contains N strings Fi, Fi will be a number X concatenate with a letter 'L' or 'R',
the number X represents the parent node index of the i_th node,
and the letter 'L' represents the ith node is the left child of index X node,
the letter 'R' on the other hand represents the ith node is the right child of the index X node.
If Fi = "0", the i_th node is the root node.

The index of node is from 1 ~ N.

It's guarantee that:
1 <= N <= 10^5
1 <= Vi <= 10^9,
and the gBST is always a valid binary tree, with no duplictate values.

Output

Output contains only 1 line.

The line contains N numbers Xi,
represent the value of the node of index i on the gBST after you mark all nodes that need to prune.
With space between the number.

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

Sample Input  Download

Sample Output  Download

Tags

Discuss