Description

Given a link list structure named Node.

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Given a list, rotate the list to the left by k places, where k is non-negative and k is smaller than the count of nodes in linked list.

For example: 
Given 1->2->3->4->5->NULL and k = 3, 
return 4->5->1->2->3->NULL.

Input

The input contains 2 sequence of positive integers.The first sequence is to create a linked list of integers, except the last one, which is -1, indicating the end of the sequence. The second line is an integer k. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Long long time ago, there's a magic kingdom call "NTHU".
Children living there need go to magic schools, "CS", when they're 13 years old.
The magic schools teach spell.

Spell have categories(詞類).

Take English for example, English have ten parts of speech, like "noun", "verb" etc.
And just like English, the spell has four parts of speech, like "Fire", "Air", "Water", and "Earth".

Besides part of speech , the spell also has its own magic grammar.

Most of the words can be classified into those four part of speech, but besides that , there are another thing in magic grammar call "spell". "Spell" means the whole sentence.

Here's a example for the grammar:
Use 1, 2, 3, 4 stands for fire, air, water, earth, and the 0 means spell, -1 means end.

Rule1: 1 1 1 -1
Rule2: 2 -1
Rule3: 3 0 4 -1

Follow the rules above , 3 2 4 -1 (water , air , earth) can be a legal spell, and so does "3 3 1 1 1 4 4 -1".

If chant it incorrectly, sometimes the spell won't work, sometimes it will blow-up.
So as a 1st grade student, the most important thing is to remember which of sententce is effective.

The homework is as following:
"Given some spell, determine whether they are effective spell or not."

Hint1 : In each grammar there is at most one "0", so it is equal to "[somthing] 0 [something]" grammar.

Hint2 : If you get RE in some testcases, you may search for "stack overflow" (堆疊溢位).

Input

First line contains two integers N, M, representing # of grammars and # of sentences.

The next N lines give the grammar. Each line contains a grammar.

The next M lines give the sentence. Each line contains a sentence.

It is guaranteed that:

• 1 ≤ N, M ≤ 100
• The length of each sentence is ≤ 100.
• There will be at most one "0" in each grammar. (For easy version)
• "0" won't appear in sentences.

Output

For each sentence output one line.

If the sentence is legal, output "True"; otherwise output "False".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The problem is to parse a series of commands to move the books that lie on the table. Initially there are n books lying on their own table (numbered from 0 to n-1, means book 0 lies on table 0) with book bi adjacent to book bi+1 for all 0 <= i < n-1

 as shown in the diagram below: 

The valid commands and limited for moving books are:

 Any command in which A = B or in which A and B are in the same stack of books is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of books.

• move A onto B

Return any books that are stacked on the top of book A and book B to their own table. Then puts book A onto book B.

• move A over B

Return any books that are stacked on the top of book A to their own table.

Then puts book A onto the top of book B.

• pile A onto B

Return any books that are stacked on the top of book B to their own table.

Then puts book A and all books on the top of book A onto the top of book B.

• pile A over B

Put book A and all books on the top of book A onto the top of book B.

• exit

Finish moving the books

Input

The input begins with an integer n on a line by itself representing the number of books in the book world. You may assume that 0 < n < 25.

 The number of books is followed by a sequence of book commands, one command per line. Your program should process all commands until the exit command is encountered.

 You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

Output

The output should consist of the final state of the books. Each table numbered i (0 <= i < n, where n is the number equal to books initial position) should appear followed immediately by a colon.

 If there is at least a book on it, the colon must be followed by one space, followed by a list of books that appear stacked in that position with each book number separated from other book numbers by a space. Don't put any trailing spaces on a line.

 There should be one line of output for each book position (i.e., n lines of output where n is the integer on the first line of input).  

 You are asked to add a new line character at the end.

Sample Input  Download

Sample Output  Download

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 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. 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.

==========

Note (2018.4.11) : (Thanks J3soon for the reminder!) There won't be any cross-subtree deletion, i.e. the following case won't happen in our testcase:

Note2 (2018.4.12) : In this problem, the expression will never be empty.

Sorry for the incompleteness of the problem description ><"

==========

Hint: If you got a TLE in the last testcase, 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:

Input

First line of input is an integer N, indicating the # of deletions.
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(個位數).

The following N lines are deletions, the format is "A B", indicating that Niflheimr wants to delete from Ath character to Bth 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 ≤ 3*10⁴
• The height of the binary tree is always ≤ 20.
• The range of deletion is always within the expression, i.e. 1 ≤ A, B ≤ length of expression
• The expression is always valid after each operation.

Output

The output consists of N+1 lines.
First line of output is the result of the original expression.
The following N lines are the results after each deletion.
Niflheimr hates big numbers, since it will make calculation more complex. So for every output, please print the result after modulo 10007 (% 10007).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The input is a postfix Boolean expression, which has at most four variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. The task is to use this postfix expression to construct a syntax tree, and print the corresponding infix expression. For example, if the input is 

AB|CD&&A|

then its syntax tree should be

The corresponding infix expression with parenthesis is 

   A|B&(C&D)|A

You need to implement the function "constructTree()" based on the two files "main.c" and "function.h" given below.

For OJ submission:

        You only need to copy and paste the code of your "function.c" into the submission block. Make sure you choose C compiler.

HINT : 

Please read partial judge code first. We help you dealing with input ：）

Input

The first line is a number N indicating the number of test cases. The next N lines contain the prefix Boolean expressions.

Output

The output contains N lines of the infix expressions with necessary parentheses.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a binary tree, find the sum of values at all leaf nodes.

Defintion of leaf nodes: nodes without any child nodes.

e.g.

        1
      /   \
     2     3
    / \     / \
   4   5 6   7
          \
           8

The answer is 4 + 8 + 6 + 7 = 25

Input

The input has three lines.

The first line contains an integer N indicating the number of nodes of the binary tree.

The second line is the inorder traversal of the binary tree.

The third line is the preorder traversal of the binary tree.

Note that there are no duplicated integers in the binary tree.

Output

Print the sum of values at all leaf nodes.

There are '\n' in the end of input

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

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