| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9260 | Tree |
|
| 9264 | Partial Sum |
|
| 9268 | Line Segments |
|
| 9272 | Max-Heap |
|
| 9276 | Can you escape? |
|
Description
Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order. Each node has unique integer identification (ID), but all IDs may not be consecutive.
Input
There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000), denoting the number of relations in the tree. In the following N lines, each line contains two integers a and b (1 <= a,b <= 1000), which means node a is node b’s parent. After that, the next line contains an integer R, which represents the root of the tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
Output
For each test case, print the pre-order of the tree. In each level, traverse the node with smaller ID first.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given n integers and q queries, in which each query defines a range, find the sum of the n given integers within this range.
Input
The first line contains an integer t, which indicates the number of test cases. In each test case, the first line contains an integer n (n<=100000), specifying how many integers will be given. The next line contains n integers, in which the ith integer represents ai (-50000 <= ai <= 50000). The followed line contains a positive integer q (q <= 10000), denoting the number of queries. Next q lines define q queries, one per line. Each query is specified by two integers a and b(1<=a<=b<=n), meaning a range, in which the partial sum of the given integers are queried.
Output
For each query, output a line with the partial sum of the given integers within the queried range.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are some line segments in 1 dimensional space. If two segments overlap or one segment’s start is another segment’s end, we consider them as one segment. Please output the length of the longest segment.
Input
There are multiple of test cases. Each case begins with an integer N (1 <= N <= 106) which represents the number of line segments. In the next N lines, each line contains two integers a and b (1 <= a <= b <= 109) representing a line segment. The input is terminated by N = 0.
Output
For each test case, output the length of the longest segment.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Please maintain a max-heap, which stores integers and is able to support following operations:
(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.
(2) POP – Delete the maximum element from the heap.
(3) TOP – Print the maximum element in the heap.
Input
There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 10000 at any time.
Output
For each “TOP” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a map, how fast can you get the two keys and then escape?
The map is a 2-dimensional grid of squares, each square is either free or filled with a wall. You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls. You have to get the two keys first and then you can go to the door. Notice that before you get the both keys, you can not pass the door.
Hint: Go to the nearest key first is not always the best choice, see the sample test cases.
Input
The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 <= R, C <= 1000) 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.
k : The position of the key.
w : The wall.
d : The door.
There are exactly two keys and exactly one door.
There is one blank line after each map. The input is terminated by two zeros in place of the map size.
Output
For each map, print one line containing the sentence "Escape in S steps.", where S is the smallest possible number of step to reach the door. If no way to reach the door, output the string "No solution." instead. One step is defined as a movement between two adjacent squares. Grabbing a key or unlocking a door does not count as a step.