| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10951 | Inversion Pair |
|
| 10952 | Suffix prefix |
|
| 10953 | Simply Fractions |
|
| 10956 | Parentheses Matching |
|
| 10957 | Mouse Maze |
|
Description
In a number sequence S = {S1, S2, S3, …, Sn}, we called (i , j) an “inversion pair” when Si > Sj and i < j. Given S, calculate the number of inversion pair in this sequence.
Input
There are several numbers of test cases. Each case begins with an integer N in a line, and then N integers N1~Nnfollow, each in a single line. The input is terminated by the number zero.
For case 1, 1<=N<=10, 0<=Ni<=100, the answer <231.
For case 2, 1<=N<=100, 0<=Ni<=106, the answer <231.
For case 3, 1<=N<=1000, -231<=Ni<231, the answer <231.
For case 4, 1<=N<=106 , -231<=Ni<231, the answer <263.
Output
For each test case, print a number of inversion pairs in the given sequence.
Hint: merge sort
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The words "waterproof" and "proofreading" have a common part "proof", which is the prefix of "proofreading" and the suffix of "waterproof". Given all possible pairs extracted from a list of words, your task is to find the length of the common suffix-prefix of a pair that is the longest one.
For example, if the list consists of "proofreading", "waterproof", and "ingredient", then the answer will be 5, since the common suffix-prefix for the pair of "waterproof" and "proofreading" contains 5 letters and is the longest, in comparison with the common suffix-prefix for the pair of "proofreading" and "ingredient", which is "ing" and has only 3 letters.
Input
The first line is an integer T (T <= 100) denoting the number of test cases. Each case starts with an integer N indicating the number of words. The next N strings are the list of the words for this test case. Each word has at most M letters, all in lower-case.
case 1: 2 <= N <= 10, 1 <= M <= 15
case 2: 2 <= N <= 20, 1 <= M <= 15
case 3: 2 <= N <= 20, 1 <= M <= 30
case 4: 2 <= N <= 30, 1 <= M <= 30
Output
The output should contain T lines for the T cases. Each line shows an integer that represents the longest length of the common part for the best choice of word pair.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given several fractions, compute their sum and express the answer in the simplest fraction form.
Input
There are many test cases in one subtask.
The first line of each test case contains an integer t, which indicates the number of fractions in the input. Each of the following t lines contains two integers a and b, which represent the numerator and the denominator of a fraction.
subtask 1 : t=2. 1<=a,b<=10.
subtask 2 : t<=5. 1<=a,b<=10.
subtask 3 : t<=5. 1<=a,b<=50.
subtask 4 : t<=10. 1<=a,b<=100.
Output
Each test case outputs one line.
The output is the sum reduced to the simplest fraction form. You need to print a '/' between the numerator and the denominator.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A string is said to be valid if it matches one of the following rules:
(1) The string is an empty string.
(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.
(3) If strings S1 and S2 are both valid, then S1S2 is valid.
Given a string consisting of parentheses, determine if it is a valid string.
Input
The first line of the input contains an integer N (N ≤ 10000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).
Output
For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.
The maze type is shown in following figure:
S$###
$$#$$
$$$##
##$$F
it consists of S (starting point), #(walls), $(road) and F (final point).
In above case, it needs 7 steps from S to F as following figure,
S$###
$$#$$
$$$##
##$$F
and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.
If there is no way from S to F, then print -1.
Input
The first line has an integer N(1<=N<=1000), which means the number of test cases.
For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.
The following R lines, each containing C characters, specify the elements of the maze.
Output
Print out the least steps for each case, and there is a new line character at the end of each line.