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: 

Book 0	Book 1	Book 2	Book 3	Book 4	Book 5	……	Book N-1
Table 0	Table 1	Table 2	Table 3	Table 4	Table 5		Table N-1

 

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
 

Demo of Moving 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

In this assignment, you have to find the maximum value in a binary tree.

The idea of solving this problem is to find the maximum value in the left sub-tree, find maximum in the right sub-tree, compare it with the root data and select the one that gives the maximum value. Like this,

max{root, max of left subtree, max of right subtree}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "function.h"
int idxSearch(int arr[], int strt, int end, int value)
{
    int i;
    for (i = strt; i <= end; i++)
    {
        if (arr[i] == value)
            return i;
    }
}

Node* newNode(int val)
{
    Node *node = (Node *)malloc(sizeof(Node));;
    node->data = val;
    node->left = node->right = NULL;
    return (node);
}

Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end)
{
    static int preorder_idx = 0;
    if(inorder_start > inorder_end)
        return NULL;
    Node *tree_node = newNode(preorder[preorder_idx++]);
    if(inorder_start == inorder_end)
        return tree_node;
    int inorder_idx = idxSearch(inorder, inorder_start, inorder_end, tree_node->data);
    tree_node->left = constructTree(inorder, preorder, inorder_start, inorder_idx-1);
    tree_node->right = constructTree(inorder, preorder, inorder_idx+1, inorder_end);

    return tree_node;
}

void destroyTree(Node *root)
{
    if(root != NULL)
    {
        destroyTree(root->left);
        destroyTree(root->right);
        free(root);
    }
}

int main(void)
{
    int *in, *pre, n, i;
    scanf("%d", &n);// get the size of tree
    in = (int *) malloc(n * sizeof(int));//allocate space for inorder
    pre = (int *) malloc(n * sizeof(int));// allocate space for preorder
    for(i=0; i<n; i++)// read in inorder
        scanf("%d", &in[i]);
    for(i=0; i<n; i++)// read in pre-order
        scanf("%d", &pre[i]);

    Node *root = constructTree(in, pre, 0, n-1);// construct trr
    printf("%d\n", maxValue(root));// print the max value of the tree
    destroyTree(root);// clean up
    free(in);
    free(pre);

    return 0;
}

function.h

#include <stdlib.h>
typedef struct treeNode
{
    int data;
    struct treeNode *left;
    struct treeNode *right;
} Node;

int idxSearch(int arr[], int strt, int end, int value);

Node* newNode(int val);

Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end);

void destroyTree(Node *root);

int maxValue(Node *tree);

All other function are provided. You only need to implement the function maxValue,

        int maxValue(Node *root)

        which gets the pointer of the tree root and returns the maximum value.

 

       You will be provided with main.c and function.h, and asked to implement function.c.

        For OJ submission:

        Step 1. Submit only your maxValue 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 tree node, second and third line are inorder and preorder of a tree respectively.

Notice that all the values are different.

Output

The maximum of a binary tree.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11359.c

Partial Judge Header

11359.h

Tags

Discuss

Description

Given a binary tree, print the inorder and postorder of the tree.

There are three common ways to traverse a binary tree recursively: inorder, preorder, and postorder. Each way contains three steps:

1. Visit the root (V)
2. Traverse the left subtree recursively (L)
3. Traverse the right subtree recursively (R)

The difference of the three ways is the order of steps, inorder is LVR, preorder is VLR, and postorder is LRV. For example, the three traversal sequences of the tree below are as follows:

This problem will give you the inorder and preorder sequences to build a tree, and you have to write two recursive functions to print the inorder and postorder of the tree.

You will be provided with main.c and function.h. main.c contains the implementation of functions which build a tree by the inorder and preorder, and function.h contains the definition of tree node. You only need to implement inorder(Node *root) and postorder(Node *root) in 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.

 

main.c

#include <stdio.h>
#include <stdlib.h>
#include "function.h"

int main(void)
{
    int *in, *pre, n, i;
    scanf("%d", &n);// get the size of tree
    in = (int *) malloc(n * sizeof(int));//allocate space for inorder
    pre = (int *) malloc(n * sizeof(int));// allocate space for preorder
    for(i=0; i<n; i++)// read in inorder
        scanf("%d", &in[i]);
    for(i=0; i<n; i++)// read in pre-order
        scanf("%d", &pre[i]);

    Node *root = constructTree(in, pre, 0, n-1);// construct trr
    inorder(root);
    printf("\n");
    postorder(root);
    destroyTree(root);// clean up
    free(in);
    free(pre);

    return 0;
}

int idxSearch(int arr[], int strt, int end, int value)
{
    int i;
    for (i = strt; i <= end; i++)
    {
        if (arr[i] == value)
            return i;
    }
}

Node* newNode(int val)
{
    Node *node = (Node *)malloc(sizeof(Node));;
    node->data = val;
    node->left = node->right = NULL;
    return (node);
}

Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end)
{
    static int preorder_idx = 0;
    if(inorder_start > inorder_end)
        return NULL;
    Node *tree_node = newNode(preorder[preorder_idx++]);
    if(inorder_start == inorder_end)
        return tree_node;
    int inorder_idx = idxSearch(inorder, inorder_start, inorder_end, tree_node->data);
    tree_node->left = constructTree(inorder, preorder, inorder_start, inorder_idx-1);
    tree_node->right = constructTree(inorder, preorder, inorder_idx+1, inorder_end);

    return tree_node;
}

void destroyTree(Node *root)
{
    if(root != NULL)
    {
        destroyTree(root->left);
        destroyTree(root->right);
        free(root);
    }
}

function.h

#include <stdlib.h>
typedef struct treeNode
{
    int data;
    struct treeNode *left;
    struct treeNode *right;
} Node;

int idxSearch(int arr[], int strt, int end, int value);
Node* newNode(int val);
Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end);
void destroyTree(Node *root);
void inorder(Node *root);
void postorder(Node *root);

Input

The input contains three lines. The first line is the number of nodes in the tree. The second line is the inorder and the third line is the preorder of the tree.

Output

The output contains two sequences of integers. The first sequence is the inorder and the second sequence is the postorder of the tree.

Notice that there is a space after every integer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11360.c

Partial Judge Header

11360.h

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