| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10475 | Set Intersection |
|
| 10476 | Inversion Pair |
|
| 10477 | K Characters |
|
| 10478 | Simply Fractions |
|
| 10479 | Islands |
|
Description
Given two sets of numbers, output their intersection set.
Input
There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set. All the numbers are 32 bit signed integers. The input is terminated if N = 0.
For case 1, 1 <= N, M <= 103
For case 2, 1 <= N, M <= 104
For case 3, 1 <= N, M <= 105
For case 4, 1 <= N, M <= 106
Output
For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print “empty” (without quotes).
Sample Input Download
Sample Output Download
Tags
Discuss
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.
Case1: 1<=N<=10^2
Case2: 1<=N<=10^3
Case3: 1<=N<=10^5
Case4: 1<=N<=10^6
Input
There are several numbers of test cases. Each case begins with an integer N (1 <= N <= 10^6) in a line, and then N integers(each number fits in 64-bit integer) follow, in a single line. The input is terminated by the number zero.
Output
For each test case, print a number of inversion pairs in the given sequence. All the answer can be fit in 64-bits integers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a string S, output all different possible set of K characters in the string. And sort them in the dictionary order.
For example, if K=2 and the given string S is ‘CDBABBD’, output
AB
AC
AD
BB
BC
BD
CD
DD
Input
The first line of input contains a positive integer T (T <= 30), which indicates the number of test cases. For each case, there is a string S and a positive integer K in a line. The length of the S is less than or equal to 100 and S contains only 'A'-'K'; The number K, less than or equal to 10, indicates the length of substrings.
For test 1: T <= 10, K <= 3, |S| <=10
For test 2: T <= 15, K <= 5, |S| <=25
For test 3: T <= 20, K <= 8, |S| <=50
For test 4: T <= 30, K <= 10, |S| <=100
T, K, |S| are all positive integers, and K <= |S| for all test cases.
Output
For each test case, output all different possible set of K characters in the string. And sort them in the dictionary order, one substring per line. Print a blank line after each test case.
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
Consider a two-dimensional array (a map) containing symbols '#' and '*'. Each '#' represents a land. If two '#'s are adjacent horizontally or vertically, then they are of the same island. Your job is to find the size of the largest island in the map.
Input
The input contains one or more maps. Each map begins with a line containing M and N, the number of rows and columns in the map. If M = N = 0, it signals the end of the input; otherwise 1 <= M <= 100 and 1 <= N <= 100.
Following this are M lines of N characters each (not counting the end-of-line characters). The characters are either '#' (land) or '*' (sea).
subtask 1~4 : 1<=N,M<=100.
Output
For each map, print the size of the largest island. Each answer is printed on a separate line.