| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9204 | Problem A (I) |
|
| 9208 | Problem B (I) |
|
| 9212 | Problem C (I) |
|
| 9216 | Problem D (I) |
|
| 9220 | Problem E (I) |
|
Description
We can encrypt a string into other string. One method is to put a string into an n×n array first, where n is the smallest number such that n2 is larger than or equal to the length of the string. Each character is put into a cell of the array, from the top left cell of the array and along neighboring cells in the counterclockwise order. The encrypted string is the output of the row major order. For example, the input string "Greed is good", whose length is 13, are put into a 4×4 array, as shown in the following figure.
The output string is "Googrd e sed i".
If the end of the encrypted string are spaces, don't output them. For example, the output of "Bass GG" is "B Ga Gss".
Input
The input consists of multiple lines. Each line is a test case, a string S with length <= 1000. The number of test case is less than 100.
case1: O(N)
case2: O(N)
case3: O(N)
case4: O(N)
N means string length.
Output
For each test case, output the encrypted string of S.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two strings, find the length of the longest common substring.
Input
The first line of input contains a positive integer t , which indicates the number of test cases. For each case, there are two strings in a line (length of the string <= 1000).
Case1: O(n3) T <= 10 , length of string <= 100
Case2: O(n2) T <= 100 , length of string <= 1000
Case3: O(n2) T <= 100 , length of string <= 1000
Case4: O(n2) T <= 500 , length of string <= 1000
Output
Output the length of the longest common substring.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are some rectangles in 2 dimensional space. We define some relations:
(1) Intersect: Choose any 2 rectangles A and B. They intersect each other if and only if there exists at least one point that can cover by the 2 rectangles. If A and B intersect, they are in the same group.
Figure 1. Sample of intersection
(2) Transitivity: Choose any 3 rectangles A, B, C. If A intersect B and B intersect C, we denote that A, B, C are in the same group.
Figure 2. Sample of Transitivity
Given the rectangles in the 2D space, please find the size of the maximum rectangle group.
Input
There are more than one cases in the input. Each case contains N rectangles in the first line of the case. In the next n lines, each line contains 4 integers: lx, ly, rx, ry. (0 <= lx, ly, rx, ry <= 1000)
lx, ly denote the left-bottom coordinate of the rectangle.
rx, ry denote the right-top coordinate of the rectangle.
Input ends with N = 0.
9212 O(N!*N) can pass this input, N <= 10
9213 O(N3) can pass this input, N <= 100
9214 O(N2) can pass this input, N <= 1000
9215 O(N2) can pass this input, N <= 1000
Output
For each test case, output the number of maximum group in one line.
Take first input for examples.
Sample Input Download
Sample Output Download
Tags
Discuss
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.
9216: O(N!*N)
9217: O(N3)
9218: O(N2)
9219: O(N2)
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
Please maintain a min-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) POPMIN - Delete the minimum element from the heap.
(3) POPMAX - Delete the maximum element from the heap.
(4) MIN - Print the minimum element in the heap.
(5) MAX - 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 5*106. You may assume that the number of elements stored in the heap will be no more than 3*106 at any time.
Case 1: For each operations O( n ), operation num:104
Case 2: For each operations O( log(n) ), operation num:106
Case 3: For each operations O( log(n) ), operation num:2*106
Case 4: For each operations O( log(n) ), operation num:5*106
Output
(1) POPMIN - In case that the heap is empty, print ”Error” instead.
(2) POPMAX - In case that the heap is empty, print ”Error” instead.
(3) MIN - Print the minimum element in the heap. In case that the heap is empty, print ”Null” instead..
(4) MAX - Print the maximum element in the heap. In case that the heap is empty, print ”Null” instead.