| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11509 | Binary Search Tree Traversal |
|
| 11510 | Can a Permutation Be Sorted By a Stack |
|
| 11511 | Can you escape |
|
| 11512 | Carry in |
|
| 11513 | Counting Sort |
|
Description
Please create a binary search tree, and support insert operation. Please ignore the repeat number and print out the tree with preorder, inorder and postorder sequence. (The root node is greater than the node in the left subtree and smaller than the node in the right subtree.)
Pre-order:
- Check if the current node is empty / null.
- Display the data part of the root (or current node).
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function
In-order:
- Check if the current node is empty / null.
- Traverse the left subtree by recursively calling the in-order function.
- Display the data part of the root (or current node).
- Traverse the right subtree by recursively calling the in-order function.
Post-order:
- Check if the current node is empty / null.
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the data part of the root (or current node).
Input
The input contains mutilple lines. The first line is an non-negative integer T (T<5) that specifies the number of testcases. The first line of each testcases is an integer N (N<=8000), and the second line contains N integer V (-32767<=V<32768). (The first number in the second line is the root.)
Output
Please print out the tree with preorder, inorder and postorder. (Totally three lines.)
Each lines has a newline character '\n' in the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Input is a permutation of 1, 2, ..., n. For instance, 3, 2, 1. We are provided with a stack, and want to ask if we supply the numbers according to the permutation order, and at each step we can either
(i) get the next number from the supply, and output the number, or
(ii) get the next number from the supply, and push the number to the stack, or
(iii) pop from the stack, and output that number.
Can we obtain the output sequence as 1, 2, 3, ..., n.
So for the case of 3, 2, 1, the answer is YES (we push, push, output, then pop, pop).
Similarly, for the case of 1, 3, 2, the answer is YES, since we output, push, output, pop.
But for 2, 3, 1, the answer is NO.
Hint:
Our strategy could be as follows.
First, we try operation (iii).
If it is invalid, then we try operation (i).
If it cannot produce what we want, try operation (ii).
If we run out of the supply and the stack is not empty. The answer is NO.
Input
There are multiple testcases in the input.
Each case contains two lines. First line contains a positive integer N indicating the length of permutation. The next line contains N distinct numbers (range 1~N) separated by a blank, which describe the given permutation.
The input is terminated by end-of-file (EOF).
Case 1: N <= 10
Case 2: N <= 100
Case 3: N <= 500
Case 4: N <= 1000
Output
For each case, outupt a single line.
If the given permutation can be sorted by a stack, output "YES", otherwise, output "NO".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a map, how fast can you find the exit and then escape?
The map is a 2-dimensional grid of squares, each square is either free or filled with a wall. The exit is hidden among one of the free spaces.
You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls and leave the range of given map.
You have to arrive the position of button first (so that the exit appears) and then you can go to the exit.
Input
The input consists of several maps. Each map begins with a line containing two integer numbers R and C specifying the map size. Then there are R lines each containing C characters.
Each character is one of the following:
s : Your start position.
. : A free square that you can move.
b : The position of the button.
w : The wall.
e : The hidden exit.
The position of start point, button and exit are guaranteed to be difference.
There are exactly one button and exactly one exit.
There is one blank line after each map. The input is terminated by end of file.
Case 1: 1 <= R, C <= 5
Case 2: 1 <= R, C <= 100
Case 3: 1 <= R, C <= 200
Case 4: 1 <= R, C <= 1000
Output
For each map, print one line containing the sentence "Escape in S steps.", where S is the smallest possible number of step to escape. If no way to escape, output the string "No solution." instead.
One step is defined as a movement between two adjacent squares. Pressing button does not count as a step.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Compute how many carries will occur when calculating the sum of two decimal numbers A and B.
Input
For each case a line, there are two positive integers A and B. There are multiple cases (<1000) terminated by EOF.
Case #1: 0<A, B<1000
Case #2: 0<A, B<10^6
Case #3: 0<A, B<10^12
Case #4: 0<A, B<10^1000
Output
For each case a line, output how many carries occur.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N integers X1, X2, ..., Xn. Please output the sorted result. (Increasing order)
Input
The input includes multiple test cases. In each test case, the first line contains one integers N. The next line contains N integers.
Hint:
The sorting algorithms in O(n lg n) don’t work.
To avoid Time Limit Exceeded in Input/Output process, try to use scanf / printf to replace cin / cout.
1 <= N <= 2*107
0 <= Xi <= 104
Output
The one line conatins many pairs. Every pair (pi,qi) means there are pi numbers whose value are qi.