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 the table with book b_i adjacent to book b_i+1 for all 0 <= i < n-1, as shown in the diagram below:

The valid commands and limited for moving books are:

Illegal commands:

• A = B
• A or B is not in the range (e.g. You cannot move or remove any book that does not exist)

All illegal commands should be ignored and should have no affect on the configuration of books.

Valid commands:

l   move A on B

Puts book A on book B.                                                                      

As below:

0 1 2 3 4

>> move 1 on 3

0 2 3 1 4

l   move A under B

Puts book A under of book B.

As below:

0 1 2 3 4

>> move 1 under 3

0 2 1 3 4

l   remove A

Remove book A from the list.

As below:

0 1 2 3 4

>> remove 1

0 2 3 4

l   exit

Finish moving the books, print the final status.

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

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

Your output should contains one line of sequence which represents the order of books from the bottom to the top.

Each number is followed by a single space. And you are asked to add a new line character at the end.

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

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

In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.

You're asked to solve this problem using circular linked list.

Input

The input has two positive integers, n (the number of people) and m (kill every m^th people).

Output

The output is the order of people that were killed.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

You are required to use linked list to do the multiplication of two polynomials.

Input

The input contains two lines. Each lines presents a polynomial. The format of each line is looked like : "5 4 -3 2 1 0" which means polynomial "5x⁴-3x²+1x^0".

Each polynomial must contain a constant term. (You can use this rule to determine whether the polynomial is end.)

For example, "-2 3 1 1 0 0" should be -2x³+1x¹.

(The input polynomial should be arrangement in descending power.)

Output

Output the answer. Print a space character in the begining.

For example, if the input is

5 4 -3 2 1 0 (means 5x⁴-3x²+1)

-2 3 1 1 0 0 (means -2x³+1x¹)

the output should be 

" -10 7 11 5 -5 3 1 1" (which means -10x⁷+11x⁵-5x³+x).

If the value of coefficient is 0, you don't have to print it.

(The output polynomial should be arrangement in descending power.)

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

The problem will ask you to create a binary search tree, and there will be 4 kinds of commands to complete

1. P : please print out the binary search tree in in-order form in th line ,if the tree is empty, please print "NULL"(There is an whitespace between each number, also after the last number,no space after NULL)

2. GetMax : print out the maximum height of the binary search tree( There need no space after output number)

3. SumLevel (input) : print out  the sum value of the nodes at the input level in the line, if the input level is bigger than the maximum height, please print out "0". ( There need no space after output number)

4. AverLevel (input) : print out the average value of the nodes at the input level in the line, please show only 3 digits after decimal point of the average numbers of level, if the input level is bigger than the maximum height, please print out "0". (You can simply use %.3f to display in such way) ( There need no space after output number)

the root level will represent as 1( for SumLevel & AverLevel, if the input level is 0, please print "0")

Input

The first line contains an integer N , which indicates the number of nodes of the binary search tree.

The second line is the data for create binary search tree

The third line contains an integer M , which indicates the number of commands.

Following line will be the input instruction

If there is same input value, please ignore the second one.

Output

There need to print newline in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss