| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11366 | Moving the books |
|
| 11846 | Construct a binary tree |
|
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.
1. 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.
2. exit
Finish moving the books
Hint: you can use following code.
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node{
int val;
struct _Node* next;
} Node;
Node* table[25];
int position[25];
void resetBook(int p2) {
}
void pileOnto(int p1, int p2) {
}
void initialize(int n) {
}
int main() {
int n;
int i;
scanf("%d", &n);
initialize(n);
while(1){
char input[100] = {0};
int p1, p2;
scanf("%s", input);
if(input[0] == 'e')
break;
scanf("%d", &p1);
scanf("%s", input);
scanf("%d", &p2);
if(position[p1] == position[p2])
continue;
resetBook(p2);
pileOnto(p1, p2);
}
Node* tmp;
for(i = 0; i < n; i++){
printf("%d:", i);
tmp = table[i]->next;
while(tmp != NULL){
printf(" %d", tmp->val);
tmp = tmp->next;
}
printf("\n");
}
return 0;
}
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 tired of constructing huge binary trees, and overwhelmed by time complexity and optimization. This time he wants to take a break.
The professor asks him to construct binary trees again QAQ. Fortunately, the problem size has reduced, thus the optimization technique in Problem 11833 (a.k.a. your homework) is no longer needed in this problem.
All you need to do is implement the build() and postorder() function!
Remember #include "function.h" and choose C compiler!
Input
*Since this problem is partial judge and the input has been handled, you don't need to care about input format.
The first line of input contains a integer N, indicating the number of nodes on the tree.
The second line contains N distinct numbers, which is the in-order traversal seuqence of the binary tree.
The third line contains N distinct numbers, which is the pre-order traversal sequence of the binary tree.
It is guaranteed that:
- 1 ≤ N ≤ 3*104
- For all x being the number on the binary tree, 1 ≤ x ≤ N.
Output
*Since this problem is partial judge and the output has been handled, you don't need to care about output format.
Print out the post-order traversal sequence of the binary tree.
There is a white space after each number (including the last one). For example, [1 2 3 4 ].
Remember to print a '\n' at the end of the output.