| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11271 | Count the Leaves |
|
| 11272 | K Characters |
|
| 11274 | GCD and LCM |
|
| 11276 | Subset Sum |
|
| 11281 | Set Intersection |
|
Description
Given a tree, count the number of leaves in this tree. 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. In the following N lines, each line has two integer a and b, indicating node a is node b’s parent. 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.
Case 1: N <= 10, 1 <= a,b <= 100
Case 2: N <= 100, 1 <= a,b <= 200
Case 3: N <= 1000, 1 <= a,b <= 2000
Case 4: N <= 1000, 1 <= a,b <= 2000000
Output
Print the number of the leaves for each test case.
Hint: All leaves have no children!
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a string S, find all different possible set of K characters in the string, and output them in dictionary order. Representation of each set in the ouput should be in alphabetical order.
For example, in the case that K=2 and the given string S is "CDBABBD", the output will be
AB
AC
AD
BB
BC
BD
CD
DD
Notice that the set {'D', 'B'} is equivalent to {'B', 'D'}.
The string "BD" in output stands for the set {'D', 'B'} or {'B', 'D'} equivalently.
Input
The first line of input is a positive integer T (T <= 30), which indicates the number of test cases.
For each test case, there are a non-empty string S and a positive integer K seperated by a space in a line. The length of S is less than or equal to 100 and S contains only upper-case letter 'A'-'K'; The number K is less than or equal to min{10, |S|}.
For dataset 1: T≤10, K≤3, |S|≤10
For dataset 2: T≤15, K≤5, |S|≤25
For dataset 3: T≤20, K≤8, |S|≤50
For dataset 4: T≤30, K≤10, |S|≤100
Output
For each test case, find all different possible set of K characters in the string, and output them in dictionary order. Output one set per line, and the representation of each set should be in alphabetical order.
Print a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given three positive integers x, y, and z, compute their greatest common divisor (GCD) and least common multiple (LCM). The GCD of two or more numbers is the largest positive integer that can divide the numbers without a reminder. The LCM of two or more numbers is the smallest positive integer that can be divided by all of the numbers without a reminder.
hint : gcd(a,b,c) = gcd(gcd(a,b),c)
Input
The first line contains a positive integer N (N<=3000), which indicates the number of test cases in the input. In the next N lines, each line contains three positive integers x, y, and z, each of which is not greater than 10^6.
case 1 : 1<=numbers <= 10^2
case 2 : 1<=numbers <= 10^3
case 3 : 1<=numbers <= 10^5
case 4 : 1<=numbers <= 10^6
Output
For each case, output the GCD and LCM of x, y, and z in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N integers, seperate all of them into two multisets A and B such that the absolute difference between their sums of elements, i.e. 
, is minimized.
Notice that:
1. Multiset is a generalization concept of a set that, unlike a set, allows multiple instances of the same element.
2. Either A or B is allowed to be empty, and the sum of elements of an empty multiset is defined as 0.
Input
Input contains multiple test cases.
Each test case starts with a positive integer N, then the next line contains N integers n1, n2, …, nN seperated by single space character. A test case of N = 0 indicates the end of input, and it should not be processed.
For dataset 1, 1≤N≤3, 0≤ni≤100
For dataset 2, 1≤N≤5, 0≤ni≤10000
For dataset 3, 1≤N≤10, 0≤ni≤100000
For dataset 4, 1≤N≤20, -1000000≤ni≤1000000
Hint: Try to enumerate all possible combinitions.
Output
For each testcase, output an integer denoting the minimum value of in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
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).