Description

Given a link list structure named Node.

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Use this structure to implement a increasing integer link list.

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.

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printList(Node *head); void freeList(Node*); int main() { Node *head = NULL; Node *temp; int data; while(1){ scanf("%d", &data); if (data >= 0) { insert_increase_list(&head, data); } else break; } printList(head); freeList(head); return 0; } void freeList(Node *head) { Node *temp; for(temp=head; temp!=NULL; temp=head) { head = head->next; free(temp); } } void printList(Node *head) { Node *temp; for(temp = head; temp!=NULL; temp=temp->next) { printf("%d ", temp->data); } printf("\n"); }

function.h

#include <stdio.h> #include <stdlib.h> typedef struct _Node { int data; struct _Node *next; } Node; void insert_increase_list(Node**, int);

Input

A non negative integer data per rows, if input is smaller then 0 then exit the while loop and exit the program.

Output

Please follow the output of program

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem will give you a sequence of positive integers.  Use this sequence to create a linked list to store those integers.  Next, the problem will give you another sequence of positive integers, p₀, p₁,…p_k-1.  Delete the nodes in the position at p₀, p₁, …p_k-1 of the linked list, where 1<=p₀<p₁<…p_k-1<=N. If the node is not existing,do nothing. And show the final results.

For example, if the first sequence is 1, 2, 3, 4, 5, 6,7, a linked list is created as

If the second sequence is 1, 1, 4, do the follows.

After p₁=1, the list becomes

because the first node is 1.  After p₂ = 1, the list becomes

because the first node is 2.  After p₃ = 4, the list becomes

because the fourth node is 6.

The framework of the program is provided.

1. Create a linked list from the input  (createList)
2. while there are still some data pi
3.     read in pi 
4.     delete node at pi  (deleteNode)
5. print the remaining list (printList)
6. free the list (freeList)

You will be provided with main.c and function.h. main.c contains the implementation of function printList, and freeList, and function.h contains the definition of node and the interface of createList(&head) and deleteNode(&head, pi).  You only need to implement createList(&head) and deleteNode(&head, pi) in function.c, in which head is the head of the linked list, and pi is the node at pi to be deleted.

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.

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printList(Node *head){ Node *temp; for(temp = head; temp!=NULL; temp=temp->next) { printf("%d ", temp->data); } } void freeList(Node *head){ Node *temp; for(temp=head; temp!=NULL; temp=head){ head = head->next; free(temp); } } int main() { Node *head; int data; head = createList(); while(1){ scanf("%d", &data); if(data>-1){ deleteNode(&head,data); }else break; } printList(head); freeList(head); return 0; }

function.h

#include <stdlib.h> #include <stdio.h> typedef struct _Node { int data; struct _Node *next; } Node; void deleteNode(Node ** nd, int data); Node* createList();

Input

The input contains 2 sequence of positive integers as the linklist and the order, except the last one, which is -1, indicating the end of the sequence. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This problem will give you a sequence of positive integers.  Use this sequence to create a linked list to store those integers.  Next, the problem will give you another sequence of positive integers, p₀, p₁,…p_k-1.  Delete the nodes that the data is equal to one of p₀, p₁, …p_k-1 of the linked list, where 1<=p₀<p₁<…p_k-1<=N. If the node is not existing,do nothing.  And show the final results.

The framework of the program is provided.

1. Create a linked list from the input  (createList)
2. while there are still some data pi
3. read in pi
4. delete node that data is equal to pi  (deleteNode)
5. print the remaining list (printList)
6. free the list (freeList)

You will be provided with main.c and function.h. main.c contains the implementation of function printList, and freeList, and function.h contains the definition of node and the interface of createList() and deleteNode(&head, pi).  You only need to implement createList() and deleteNode(&head, pi) in function.c, in which head is the head of the linked list, and pi is the data of the node to be deleted.

For OJ submission, you only need to submit your createList and deleteNode implementation to the submission block. (Choose c compiler) 

Below is the partial code for main.c

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printList(Node *head){ Node *temp; for(temp = head; temp!=NULL; temp=temp->next) { printf("%d ", temp->data); } } void freeList(Node *head){ Node *temp; for(temp=head; temp!=NULL; temp=head){ head = head->next; free(temp); } } int main() { Node *head; int data; head = createList(); while(1){ scanf("%d", &data); if(data>-1){ deleteNode(&head, data); }else break; } printList(head); freeList(head); return 0; }

function.h

#include <stdlib.h> #include <ctype.h> typedef struct _Node { int data; struct _Node *next; } Node; void deleteNode(Node **, int); Node* createList();

Input

The input contains 2 sequences of positive integers.  The first sequence is to create a linked list of integers, and the second sequence is the nodes to be deleted.  Each sequence is ended by -1. 

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

Partial Judge Header

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

Partial Judge Header

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

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 which output equal to 1.

For example, if input is "&|AB|CA", then result will be

A B C D output

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 4 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Give a prefix expression, which only has 2 operators, ‘+’ and ‘-’,and positive integers. Print the result.

Input

The input contains a sequences of prefix expression. It contains operators, ‘+’ and ‘-’,and positive integers separated by a space. Expression is ended by 0. (0 is not the element.)

Output

The output is the result of the expression. (Without a newline symbol)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a binary tree, print the sum of nodes in the tree.

This problem will give you the inorder and preorder sequences to build a tree, and you have to write a function to count the sum of nodes in the tree. To solve this problem, you can write a recursive function to traverse the tree and sum up the data of nodes.

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 Sum(Node *root) and print the sum 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 printf("%d", Sum(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); int Sum(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 is the sum of nodes in the tree.

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

Input

Output

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

The Josephus problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

Given a group of  n men arranged in a circle under the edict that every m man will be executed going around the circle until only one remains. Find the position in which you should stand in order to be the last survivor.

Input

Each line with 2 integers, n, m. n is the number of people. m is the number that every m person is executed. Input terminated by EOF.

Output

The output will consist in separate lines containing the position of the person which life will be saved. Each line should be ended with a newline character '\n'.


Sample Input  Download

Sample Output  Download

Tags

Discuss