| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9300 | Longest Common Substring (I) |
|
| 9304 | Pascal(I) |
|
| 9308 | Base(I) |
|
| 9312 | Postfix Evaluation |
|
| 9316 | Can You Escape? |
|
Description
Given two strings, find the length of the longest common substring.
Input
The first line of input contains a positive integer t (t <= 100), which indicates the number of test cases. For each case, there are two strings in a line (length of the string <= 1000).
case 1: length of the string <= 30
case 2: length of the string <= 100
case 3: length of the string <= 1000
case 4: length of the string == 1000
Output
Output the length of the longest common substring.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Pascal sequence of order n generates n integers, in which the kth element is defined as 
For example: if n = 3, the sequence is 1 3 3 1.
Following is the illustration of the pascal triangle.
1 --> 0
1 1 --> 1
1 2 1 --> 2
1 3 3 1 --> 3
1 4 6 4 1 --> 4
...
...
...
Input
There will be multiple test cases. No number of test cases is given. Each case is given in a single lines, containing an integer n (1 <= n <= 1000).
case 1: n<=20
case 2: n<=100
case 3: n<=500
case 4: n<=1000
Output
For each case, output the Pascal sequence. Two consecutive numbers are separated by a space. All numbers should be mod by 1000007.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a decimal integer n and a base k, translate n to the corresponding k-based number.
Input
The first line contains an integer t (1 <= t <= 100), which indicates the number of test cases in the input. Each test case is given in a line, containing two integers n and k (n <= 10000000, k<=9).
case1: n<=100
case2: n<=10000
case3: n<=100000
case4: n<=10000000
Output
Output the number in base k.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Evaluate the result of a given numerical expression written in postfix notation.
Input
There are many test cases. Each line represents a test case.
Each line has a numerical expression written in postfix notation, and the number of “characters” in a line will not greater than 10^5.
Every number in input will fit in 32-bit signed integers.
The operators contain only “+”,”-“,”*”and”/”, and the division “/” here is considered as integral division.
Output
The output of each test case occupies a line. Each line begins with the test case number”Case i:”, and then a space character followed by the evaluated answer.
The answer will fit in 64-bit number.
However, if the expression is invalid, please print “Case i: error!”.
It’s guaranteed that in the first and second test case, there are all valid expressions.
9312 : all expressions are valid.
9313 : all expressions are valid.
9314 : some expressions are invalid.
9315 : some expressions are invalid.
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 (1 <= R, C <= 4000) 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.
9316: O( 4(R*C) ) can pass this case
9317: O( (R*C)2 ) can pass this case
9318: O( (R*C) lg (R*C) ) can pass this case
9319: O( R*C ) can pass this case
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.