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

There are N numbers in a queue.  The origin sequence is from 1 to N. (1 is the head). The operation “Move a b” means to move all the numbers in front of a (including a) and then insert them in front of b without changing order.  Given several such operations and output the final status of the sequence.

Input

There will be only one test case. The test case begins with an integer N indicating the number of people.  There are several operations followed.  The format is “Move a b” (without quote) you can assume that the position of a is in front of the position of b.  The test case is terminated by “Exit” (without quote).

subtask 1 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 2 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 3 : 1<=N<=100000, you need use O(1) algo for each operation.

subtask 4 : 1<=N<=1000000, you need use O(1) algo for each operation.

Output

Output the numbers from the first one to the last one, and separate two consecutive numbers by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please compute the sum of two given n-bit binary numbers.

Input

The first line of the input file contains a positive integer t indicating the number of test cases. The first line of each test case is a positive integer n denoting the length of bits. The second and third lines are the two n-bit binary numbers. The first bit of each binary number is always 0, which guarantees that the sum of the two binary numbers can still be expressed as an n-bit binary number.

Case1 : t<=100, n<=100
Case2 : t<=200, n<=1000
Case3 : t<=300, n<=5000
Case4 : t<=400, n<=10000

Output

For each test case, your program should print the sum in the same format as the binary numbers given in input.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Assume that we need to send a stream of data items as a series of packets. The size limit of a packet is M, and each item i has a size s_i satisfying s_i < M, for i = 1, 2, ....N
For each item i, we can append it to the current packet as long as the total size of the items in the packet does not exceed the limit; otherwise, we put the item into a new packet. 
Our task is to simulate the process and decide how many packets are needed.

Case1: 0<M<=1*10², 0<=N<=20
Case2: 0<M<=2*10⁴, 0<=N<=100
Case3: 0<M<=1*10⁵, 0<=N<=10000
Case4: 0<M<=2*10⁹, 0<=N<=10000

Input

The input consists of several test cases.
Each test case starts with an integer M indicating the size limit of a packet.
The subsequent positive integers enumerate the sizes of the items, and a number 0 denotes the end of the current stream.

Output

The output contains several lines.
Each line prints the number of packets needed to send the stream for the corresponding test case.
Each line is ended with a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You need to write a program to simulate a queue of names.  Each name is a string consisting of English letters only.  There are three operations:

1.         “Push [name]”, which means to enque name in the queue.

2.         “Pop”, which means to deque. If the queue is empty, this operation takes no effect.

3.         “Front”, which means to print out the name in the front of queue. If the queue is empty, print "empty" (without quotes).

Case1 : #operation <= 10^2, There will be no "Pop" and "Front" command when queue is empty.
Case2 : #operation <= 10^3. There will be no "Pop" and "Front" command when queue is empty.
Case3 : #operation <= 10^4.
Case4 : #operation <= 10^6.

Input

Each line contains one of the following operations. “Push [name]” (without quotes), “Pop” (without quotes), “Front”(without quotes). The length of each name is at most 10.

Output

For each “Front” operation, print out the name in the front of the queue.

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).

Case 1 : N≤50

Case 2: N≤100

Case 3: N≤1000

Case 4: N≤10000

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

Given a sequence S of digits and a number k, for example S = “4113” and k = 2.
In the sequence S, there is one 4, followed by two 1, followed by one 3. 
Then we can produce a new sequence S’ = 142113.
(note : 
“one 4” -> 14
“two 1” -> 21
“one 3” -> 13
)

This is the first round, and we need to do it for k rounds.

The input of i round is the output from i-1 round. (i>1)
When i = 1, the input is sequence S, we will give you.

Now, we want you to print the output after k rounds.

Another example : 

S = "323", and k = 1

then we have one 3,followed one 2, and followed one 3

so S' would be "131213"

(note:

"one 3" -> 13

"one 2" -> 12

"one 3" -> 13

)

Input

The input includes multiple test cases. 
The first of the input is an integer T (T <= 1000) specifying the number of test cases. 
For each case, the first line contains the sequence S.
The second line contains one integer k.

limits 
Case 1 : length of S <= 5, 1<=k<=2
Case 2 : length of S <= 100, 1<=k<=2
Case 3 : length of S <= 1000, 1<=k<=10
Case 4 : length of S <= 1000, 1<=k<=10

Output

For each test case outputs one line, the output after k rounds.  

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a list of English words. Output them in lexicographic order. We compare the first character of two strings S1 and S2. If the ASCII code of the first character of S1 is smaller than the first character of S2, we said that S1 is smaller than S2. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order.  If S1 is S2’s prefix, S1 is smaller than S2 and vice versa.

Input

There are multiple test cases.  Each case begins with an integer N in a line, and then N words follow, each word in a line.  The maximum length of words is 50.  The alphabets are 26 small English letters ‘a’ to ‘z’. The input is terminated if N = 0.

Case 1: 1 <= N <= 10
Case 2: 1 <= N <= 100
Case 3: 1 <= N <= 500
Case 4: 1 <= N <= 1000

Output

For each test case, print the words in lexicographic order, one word per line.
Print a blank line after each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two vectors of numbers, output their intersection set.

Note: the numbers of vectors need not to be unique.

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 <= 10³
For case 2, 1 <= N, M <= 10⁴
For case 3, 1 <= N, M <= 10⁵
For case 4, 1 <= N, M <= 10⁶

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).

Note: There's a newline character at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss