四川理工学院

2010年大学生程序设计竞赛

试 题

1. Matching brackets

Suppose an arithmetic expression can contain three types of brackets: the parentheses "(" and ")", the square brackets "[" and "]" and the curly braces "{" and "}". And they can use a random nested order (such as :...[...{...}...[...]...]...[.....]...(...) ...). Please code an algorithm to judge that, in a given expression ( that have be placed into a sequential list that has characters as data elements), the brackets are match correctly or not.

Sample Input：

1 ...[......{....[...]...(...)...(....[...]...)..}...(...)...[...]....]

2 ...[...(...{...)....}...[...]....(.....)...]

3 ...[...(...{...(...)...[....]...)...]

Sample Output：

1 right

2 wrong（the sequnce is not right）

3 wrong（the number is not right）

2. Path in Graph

In a directed graph G, which is stored as an adjacent matrix, from the vertex i to the vertex j, programming for counting the routes of which length is k and that have no ring.

PS: There is an expression, which is called as adjacency matrix, of graph.

The number in the matrix is the distance between the nodes. As the follows:

dij= a when there is a line weights a between node Vi and Vj;

dij=∞when there is no line between node Vi and Vj.

Sample Input：

From vertex V1 to vertex V3, length is 12

From vertex V4 to vertex V1, length is 9

Sample Output：

1

1

3. Digital Roots

The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.



For example, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yeilds 3, a single digit and also the digital root of 39.

Input

The input file will contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of zero.

Output

For each integer in the input, output its digital root on a separate line of the output.

Example

Input

24

39

0

Output

6

3

Test

Input

26

159

72

0

Output

8

6

9

4. Adding Reversed Numbers

The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.

ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).

Input

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

Output

For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.

Sample Input

3

24 1

4358 754

305 794

Sample Output

34

1998

1

Test

Input

2

159 245

78 32

Output

3941

11

5. Fraction to Decimal

Write a program to print the decimal ,which equaled to the fraction mark N/D(N as the numerator, D as the denominator).Use brace to include it if the decimal is infinite cycle.

Sample Input

Fraction:1/3

Fraction:22/5

Fraction:1/7

Fraction:3/8

Sample Output

Decimal: .(3)

Decimal: 4.4

Decimal: .(142857)

Decimal: .375

6. Sort of Fraction

Given all the fractions which values are between 0 and 1.And their denominators are not more than N. Write a program to print these fractions from the minimum to the maximum and the totle number with N(1<=N<=100).

Sample Input

Enter the max denominator:5

Sample Output

The sequence: 0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1

The totle number is: 11.

7. Find seat

Xiao bai go to library for self-sutdy. There are many people in library ，it’s difficult to find a satisfied seat. These are his demands for a seat:

1. First, there must have 2 contiguous empty seat in one line, because his classmate Xiao hei will come to library and seat next to him .

2. Xiao bai want a quiet seat, so he want there are no people around. (front ,back , left , right)

3. More far away from the aisle is more good.( there are two aisles )

4. More latter more good.

So, the best seat for Xiao bai is in the middle of the last line and there is no people around, but the seat may be occupied. Now , Xiao bai need your help, to find a seat that satisfied his demands as far as possible.

Input:

1. The line from front to back has the serial number , stars from 0, the last is M-1

2. The serial number of seat every line is 0….N-1 from left to right

3. Use character ‘E’ to indicate a seat is empty, or ‘P’ , has people. The library ‘s situation is stored in file, and two number at the first line is the line number and the seat number.

Output:

Output the position of the seat ( line, row), print -1 if there is no seat satisfied.

Sample input:

5 10

EPPPEPEPEP

PEEEPEEEEP

EPPEPPEEPP

PEEEPEPPEE

EEEEPPEPPE

Sample output:

line:4 row:2