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

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

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

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

Discuss

Description

Disclaimer : This problem has nothing to do with MST(Minimum Spanning Tree). You don't need solid algorithm basic to solve this problem.

After doing a bunch of dull tree problems, you become dizzy and the trees look like they are spinning in your view.

You see an expression tree. The tree in your view can spin in two directions:

• Left Spin : For a tree rooted at node P, of which right child is node Q and the left child of Q is B, after a left spin, the new root becomes Q, the left child of Q becomes P, and the right child of P becomes B. If P doesn't have a right child (i.e. Q is null), left spin cannot be performed.

• Right Spin : For a tree rooted at node Q, of which left child is node P and the right child of P is B, after a right spin, the new root becomes P, the right child of P becomes Q, the left child of Q becomes B. If Q doesn't have a left child (i.e. P null), right spin cannot be performed.

After several (or zero) times of spinning, if the expression tree can still denote a valid expression, we say that the tree is a good spinning tree; otherwise we say that the tree is a bad spinning tree.

The evaluation of the tree changes after the tree spins. Given an evaluation tree, you want to know that what is the minimum evaluation among all good spinning trees.

Explanation of Sample IO

For the given expression tree, it has four good spinning trees which are shown in the below figure. Initially its evaluation is -8. After one left spin, its evaluation becomes 0. After two left spins, its evaluation becomes -6. After one right spin, its evaluation becomes 0. It is obvious that after three left spins or two right spins, the tree cannot donate a valid expression. Therefore the minimum spinning tree is the inital tree and therefore output -8.

Input

The first line of the input is an integer N(3 <= N <= 3x10⁵), being the length of the prefix expression of the expression tree.

The next line is the expression tree (in prefix expression). The expression contains only +, -, * and digits. All the numbers in the expression are integers between 1 and 9.

Test Cases

• For all test cases, it is guaranteed values during calculation is between [-10⁹, 10⁹], meaning that using 32-bit integer will not overflow (if your code does not have bugs).

• 1-st test case : same as sample IO

• 2-nd test case : N <= 50. It is guaranteed that there are only three good spinning trees : the giving tree, the tree that left spins once, and the tree that right spin once. (i.e. evaluate the three good spinning trees and output the minimum value, and then you get AC in this test case)

• 3-rd, 4-th test case : You can get AC using an O(N²) solution.

• 5-th test case : You need to come up with an O(N) solution to get an AC.

Output

Output the minimum evaluation among all good spinning trees.

Note that you should have a '\n' in the end.

Sample Input  Download

Sample Output  Download

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

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

Discuss

Description

Important Note

This is a partial judge problem. You only need to implement the required functions. The judge will provide main.c and function.h, read the input, call your functions, and check the output.

Before submitting your code:

1. You must submit implementations for all required functions. The function body may be empty, but the function must exist.
2. You must submit all header files you use.

Otherwise, you may receive a Compile Error.

Problem Statement

You need to maintain a multiset of lowercase English strings. All strings consist only of lowercase English letters a to z. The same string may be inserted multiple times. Each occurrence is counted separately.

You need to implement a trie, also called a prefix tree, to support the following functions.

Trie

A trie is a tree data structure for storing strings. Each edge represents one character. A path from the root to a node represents a prefix.

For example, suppose the current strings are:

app
apple
ape
bat

The trie can be visualized as follows:

root
|-- a
|   `-- p
|       |-- p  (app)
|       |   `-- l
|       |       `-- e  (apple)
|       `-- e  (ape)
`-- b
    `-- a
        `-- t  (bat)

In this trie, the prefix ap is shared by app, apple, and ape. Therefore, there are 3 strings with prefix ap.

Suggested Node Information

The header file defines a trie node as follows:

typedef struct Node {
    int pass_count;
    int end_count;
    struct Node *child[26];
} Node;

The value pass_count is useful for prefix counting. The value end_count is useful for checking whether the current path is a complete string.

Provided Function

The judge provides the following function:

Node* create_node(void);

This function creates and returns a new empty trie node. The judge's main.c will call this function once to create the root before any operation is processed. You may also call this function inside insert_string when a new child node is needed. You do not need to implement create_node.

Required Functions

1. Insert

Insert one occurrence of string s into the multiset.

void insert_string(Node *root, char s[]);

The string s contains only lowercase English letters.

2. Delete

Delete one occurrence of string s from the multiset.

void delete_string(Node *root, char s[]);

It is guaranteed that at least one occurrence of s currently exists.

3. Count Prefix

Return the number of strings currently in the multiset that have p as a prefix.

int count_prefix(Node *root, char p[]);

4. Get Minimum String

Write the lexicographically smallest string currently in the multiset into ans.

void get_min_string(Node *root, char ans[]);

It is guaranteed that the multiset is not empty when this function is called. The output string must be null-terminated.

5. Get Maximum String

Write the lexicographically largest string currently in the multiset into ans.

void get_max_string(Node *root, char ans[]);

It is guaranteed that the multiset is not empty when this function is called. The output string must be null-terminated.

Lexicographical Order

Lexicographical order is the usual dictionary order. For example:

ape < app < apple < bat

If one string is a prefix of another string, the shorter string is smaller. For example:

app < apple

Input

The judge's main.c reads the input and calls your functions.

The first line contains one integer Q, the number of operations.

Each of the next Q lines contains one operation in one of the following formats:

1 s
2 s
3 p
4
5

The meaning of each operation is:

• 1 s: call insert_string(root, s).
• 2 s: call delete_string(root, s).
• 3 p: call count_prefix(root, p) and print the returned value.
• 4: call get_min_string(root, ans) and print ans.
• 5: call get_max_string(root, ans) and print ans.

Constraints

1 <= Q <= 200000
1 <= |s|, |p| <= 100
The total length of all inserted strings and queried prefixes is at most 5 * 10^6.

• All strings contain only lowercase English letters a to z.
• The total length includes strings in operations 1 s and prefixes in operations 3 p. Strings in delete operations 2 s are not counted again.
• For every operation 2 s, at least one occurrence of s currently exists.
• For every operation 4 or 5, the multiset is not empty.
• The same string may appear multiple times in the multiset.

Output

The output is produced by the judge's main.c according to the return values or answer strings produced by your functions.

For each operation 3 p, output one integer: the return value of count_prefix(p).

For each operation 4, output one string: the string written by get_min_string(ans).

For each operation 5, output one string: the string written by get_max_string(ans).

Each answer is printed on its own line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

Red cape flying cat wrote a small calculator. The calculator can process expressions containing non-negative integers, +, -, *, and parentheses.

However, his calculator does not understand the custom operators @ and $. Before giving an expression to the calculator, you need to replace every custom operator with an equivalent expression using only ordinary operators.

Definition

The custom operators are defined as:

a @ b = a - (a * b) + b
a $ b = (a @ b)

Therefore:

a $ b = (a - (a * b) + b)

Here, a and b are both factors.

In this problem, a factor is:

FACTOR = NUMBER | (EXPR)

That is, a factor is either a non-negative integer or a parenthesized expression.

For each custom operator, its left operand is the nearest valid factor immediately on its left, and its right operand is the nearest valid factor immediately on its right.

Replacement Rule

You must repeatedly perform the following operation:

1. Find the leftmost custom operator, either @ or $, in the current expression.
2. Let a be the nearest factor on its left.
3. Let b be the nearest factor on its right.
4. If the operator is @, replace a@b with a-(a*b)+b.
5. If the operator is $, replace a$b with (a-(a*b)+b).

After a replacement, the new expression becomes the current expression. Continue until there is no custom operator left.

The final expression must contain only digits, +, -, *, (, and ). Do not output spaces.

Examples

For:

2@3

The result is:

2-(2*3)+3

For:

2$3

The result is:

(2-(2*3)+3)

For:

(2+3)@4

The left factor is (2+3), and the right factor is 4, so the result is:

(2+3)-((2+3)*4)+4

For:

2*3@4

The left factor of @ is only 3, not 2*3. Therefore, the result is:

2*3-(3*4)+4

For multiple custom operators, always replace the leftmost one first:

2@3$4
=> 2-(2*3)+3$4
=> 2-(2*3)+(3-(3*4)+4)

Partial Judge

This is a partial judge problem. The judge provides main.c and function.h.

You only need to implement:

void replace_custom_operator(char expr[], char result[]);

expr is the original expression. You should store the final expression in result. The judge will print result.

The provided function.h also contains suggested helper function names used by the reference solution. You do not have to use exactly those helper functions, but they may help you split the implementation into smaller parts.

Input

The input is read by the judge's main.c.

The input contains one line: a valid expression expr.

Constraints

1 <= |expr| <= 2000
0 <= NUMBER <= 1000000000
After replacing all custom operators, the expression length will not exceed 50000.

• The expression contains only digits, +, -, *, @, $, (, and ).
• The expression is valid.
• There are no spaces in the expression.
• Unary minus will not appear in the input.

Output

The output is produced by the judge's main.c.

Output the expression after replacing all custom operators.

The output should not contain spaces.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

Qsort, Linked List, Binary Tree, Tree Traversal, Expression Order, Syntax Tree, and Recursive Parsing

1. qsort

To use qsort, you have to include <stdlib.h>.

Usage

void qsort(void *array, size_t count, size_t size, comparison_fn_t compare);

qsort an int array

int compare_int(const void *a, const void *b)
{
    const int *va = (const int *)a;
    const int *vb = (const int *)b;

    return *va - *vb;
}

qsort a double array

int compare_double(const void *a, const void *b)
{
    const double *da = (const double *)a;
    const double *db = (const double *)b;

    return (*da > *db) - (*da < *db);
}

2. Linked List

Node Definition

typedef struct _Node {
    int data;
    struct _Node *next;
} Node;

Print the Content of the Linked List

void printList(Node *head)
{
    Node *temp;

    for (temp = head; temp != NULL; temp = temp->next) {
        printf("%d ", temp->data);
    }
}

Insert a Node After the Node Pointed by nd

Return 1 if insertion succeeds. Otherwise, return 0.

int insertNode(Node* nd, int data)
{
    if (nd != NULL) {

        Node* temp = (Node*)malloc(sizeof(Node));

        temp->data = data;
        temp->next = nd->next;
        nd->next = temp;

        return 1;
    }

    return 0;
}

Delete a Node After the Node Pointed by nd

Return 1 if deletion succeeds. Otherwise, return 0.

int deleteNode(Node* nd)
{
    if (nd != NULL) {
        Node* temp = nd->next;

        if (temp != NULL) {
            nd->next = temp->next;
            free(temp);

            return 1;
        }
    }

    return 0;
}

3. Binary Tree

Binary Tree Node Definition

typedef struct _node {
    int data;
    struct _node *left, *right;
} BTNode;

4. Tree Traversal

5. Expression Order

6. Syntax Tree

In a syntax tree, the internal nodes are operators, and the leaves are operands.

7. Recursive Evaluation of Prefix Expression

The following is pseudo code for evaluating a prefix Boolean expression.

int evalBoolExpr()
{
    char c = getchar();

    if (c is an operator) {

        op1 = evalBoolExpr();
        op2 = evalBoolExpr();

        return op1 c op2;

    } else if (c is a variable) {

        return the value of c;
    }
}

8. Grammar of Infix Expression with Parentheses

EXPR   = FACTOR | EXPR OP FACTOR
FACTOR = ID | (EXPR)

9. Syntax Tree Construction from Infix Expression

Suppose expr[] is an array of expression and pos is the current position, which is initially strlen(expr) - 1.

Create a New Tree Node

BTNode* makeNode(char c)
{
    int i;

    BTNode *node = (BTNode*)malloc(sizeof(BTNode));

    /* set node->data */
    node->data = c;

    node->left = NULL;
    node->right = NULL;

    return node;
}

Parse FACTOR

BTNode* FACTOR()
{
    char c;
    BTNode *node = NULL;

    if (pos >= 0) {

        c = expr[pos--];

        if (c is an ID) {

            node = makeNode(c);

        } else if (c == ')') {

            node = EXPR();

            if (expr[pos--] != '(') {
                printf("Error!\n");
                freeTree(node);
            }
        }
    }

    return node;
}

Parse EXPR

BTNode* EXPR()
{
    char c;

    BTNode *node = NULL;
    BTNode *right = NULL;

    if (pos >= 0) {

        node = right = FACTOR();

        if (pos > 0) {

            c = expr[pos];

            if (c is an operator) {

                node = makeNode(c);

                node->right = right;

                pos--;

                node->left = EXPR();
            }
        }
    }

    return node;
}

Input

Output

Sample Input  Download

Sample Output  Download

Discuss