| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9380 | Longest Common Substring |
|
| 9384 | Polynomial Addition |
|
| 9388 | All combinations |
|
| 9392 | Parentheses Matching |
|
| 9396 | Suffix prefix |
|
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).
Output
Output the length of the longest common substring.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two polynomials please calculate the result of adding these two polynomials.
A = Cnxn + Cn-1xn-1 + ... + C0
B = C'mxm + C'm-1xm-1 + ... + C'0
Input
The first line contains an integer t (1 <= t <= 5000), which indicates the number of test cases in the input. For each case, the first line contains two integers n, m(0 <= n, m <= 1000). Integer n means the highest power of the first polynomial. Integer m means the highest power of the second polynomial. In the next 2 lines, the first line contains n+1 integers, which means the coefficients of the polynomial A from high to low. The second line contains m+1 integers, which means the coefficients of the polynomial B from high to low. All coefficients are integers less than 105 and might be negative.
Output
For each case, output a line with the coefficients of the polynomial A+B. There is a space between two consecutive numbers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N different hexadecimal digits. You have to choose M from them to create all possible numbers in ascending order. For example, given 3 digits "1", "5", "D", and M = 2, the possible answers are "15", "1D", "51", "5D", "D1", "D5".
Input
The first line contains a positive integer T (T <= 100), which indicates how many cases in the input. Each case starts with two positive integers N and M (1 <= M <= N <= 16), which denote the amount of the digits and the amount of digits of desired numbers. The next line contains exactly n different digits(0~F) separated by blanks.
Case 1: 1 <= M <= N <= 10, digit range (0~9), T <= 10
Case 2: 1 <= M <= N <= 10, digit range (0~F), T <= 10
Case 3: 1 <= M <= N <= 10, digit range (0~F), T <= 20
Case 4: 1 <= M <= 10, 1 <= N <= 16, digit range (0~F), T <= 20
Output
For each case, first line outputs the case number. Then, output all the possible numbers in ascending order. (See the Sample Output)
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 ≤ 1000) 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).
case 1: 2 <= N <= 10
case 2: 2 <= N <= 100
case 3: 2 <= N <= 500
case 4: 2 <= N <= 1000
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
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.