Description

There is a list of English words. Output them in lexicographic order. We compare the first character of two strings S1and 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.

Hint: Because of large input size, please use scanf and printf for efficiency.

Input

There are multiple test cases.  Each case begins with an integer N (1 <= N <= 1000) 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.

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Adding decimal (十進位制) numbers seems like a piece of cake for human beings. In this problem, 2 positive integers, A and B, are given, and you are asked to output the sum to these integers, and the number of carries while adding.

A carry happens when the result of the addition of certain digit is greater than 9. In that case, the higher digit will receive the additional 1 when adding. See the following case:

Carry     1     1 1 1
A           7 1 2 3 4 5
B           7 8 6 6 8 5 
      +)________________
Sum       1 4 9 9 0 3 0

So, the sum is 1499030 and the number of carries is 4.

Input

There are multiple test cases.

Each with 2 positive integers, A and B, are given in a line and separated by a space.

Case#1: 0<A, B<10³

Case#2: 0<A, B<10⁸

Case#3: 0<A, B<10¹⁶

Case#4: 0<A, B<10¹⁰⁰⁰

Output

Print the sum and number of carries in a line, and separate them with space. And print a new line ('\n') character at the end of your answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given N integers X1, X2, ..., Xn. Please output the sorted result. (Increasing order)

Input

The input includes multiple test cases. In each test case, the first line contains one integers N. The next line contains N integers.

Hint:

The sorting algorithms in O(n lg n)  don’t work.

To avoid Time Limit Exceeded in Input/Output process, try to use scanf / printf to replace cin / cout.

1 <= N <= 2*10⁷

0 <= Xi <= 10⁴

Output

The one line conatins many pairs. Every pair (pi,qi) means there are pi numbers whose value are qi.

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

Please write a program to find out that whether a directed graph has cycles.

Input

There are many cases in input.

The first line in the input contains two integers: n, m, representing the number of nodes in the graph and the number of edges in the graph.
The next m lines, each line contains 2 integers, u and v (1<= u, v <= n). That means there is an edge from u to v(v to u has no edge).
Input will be terminated by EOF (End-Of-File).

There has no node connected to itself!!

Problem size 
Input1: 1 <= n <= 10

Input2: 1 <= n <= 100 

Input3&Input4: 1 <= n <= 1000

0 <= m <= n*(n-1)

Input 1: O(n!) can pass this
Input 2: O(n^3) can pass this
Input 3&Input 4: O(n^2) can pass this 

Output

For each case, print YES if there has at least one cycle in the graph, otherwise, print NO.

Sample Input  Download

Sample Output  Download

Tags

Discuss