华东师范大学计算机科学技术系

Problem D: GCD and LCM

Description Write a program which computes the greatest common divisor(GCD) and the least common multiple(LCM) of given a and b (0<=a,b<=44000).

Input The first line of input gives the number of cases, N(1<=N<=100). N test cases follow. Each test case contains two integer a and b separated by a single space in a line.

Output

For each test case, print GCD and LCM separated by a single space in a line.

Sample Input 2 8 6

5000 3000

Sample Output 2 24

1000 15000

Page 5 / Total 9

华东师范大学计算机科学技术系

Problem E: sort it?

Description

There is a database, partychen want you to sort the database’s data in the order from the least up to the greatest element, then do the query: “ which element is i-th by its value?- with I being a natural number in a range from 1 to N.

It should be able to process quickly queries like this.

Input

The standard input of the problem consists of two parts. At first, a database is written, and then there’s a sequence of queries. The format of database is very simple: in the first line there’s a number N(1<=N<=10000), in the next N lines there are numbers of the database one in each line in an arbitrary order. A sequence of queries is written by simply as well: in the first line of the sequence a number of queries K (1<=K<=100)is written, and in the next K lines there are queries one in each line. The query “which element is i-th by its value?” is coded by the number i.

Output

The output should consist of K lines, in each lines there should be an answer to the corresponding query, the answer to the query “I”is an element from the database, which is i-th by its value(is the order frome the least up to the greatest element).

Sample input 5 7 121 123 7 121 3 3 2 5

Sample output 121 7 123 Hint

After we sort the date we get 7 7 121 121 123,so the position 3 is 121, the position 2 is 7 and the position 5 is 123 etc.

Page 6 / Total 9

华东师范大学计算机科学技术系

Problem F: Hub Connection plan

Description

Party Chen is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each worker of the company must have access to the whole network, each hub must be accessible by cables from any other hub(with possibly some intermediate hubs).

Since cables of different types are available and shorter ones are cheaper, it is necessary to make such a plan a plan of hub connection, that the cost is minimal. partychen will provide you all necessary information about possible hub connections. You are to help partychen to find the way to connect hubs so that all above conditions are satisfied.

Input

The first line of the input contains two integer numbers:N-the number of hubs in the network(2<=N<=1000)and M-the number of possible hub connections (1<=M<=15000).All hubs are numbered from 1 to N. the following M lines contain information about possible connections- the numbers of two hubs, which can be connected and the cable cost required to connect them. Cost is a positive integer number that does not exceed 1000000. there will always be at least one way to connect all hubs.

Output

Output the minimize cost of your hub connection plan.

Sample input 4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1

Sample output 3 Hint

We can build net from 1 to 2 to 3 to 4. then we get the cost is 3. Of course you can get 3 by other way.

Page 7 / Total 9

华东师范大学计算机科学技术系

Problem G: Principles of Compiler

Description After learnt the Principles of Compiler, Party Chen thought that he can solve a simple expression problem. So he gives you strings of less than 100 characters which strictly adhere to the following grammar (given in EBNF): ● A:=’(’B’)’|’x’. ● B:=AC.

● C:={’+’A}.

Can you solve them too?

Input The first line of input gives the number of cases ,N(1<=N<=100),N test cases follow. The next N lines will each contain a string as described above.

Output

For each test case, if the expression is adapt to the EBNF above output “Good”, else output “Bad”.

Sample input 3 (x)

(x+(x+x)) ()(x)

Sample output Good Good Bad

Page 8 / Total 9

华东师范大学计算机科学技术系

Problem H: Separate Connections

Description

Partychen are analyzing a communications network with at most 18 nodes. Character in a matrix i,j(I,j both 0-based,as matrix[i][j]) denotes whether nodes I and j can communicate(‘Y’for yes, ‘N’for no). Assuming a node cannot communicates with two nodes at once, return the maximum number of nodes that can communicates simultaneously. If node i is communicating with node j then node j is communicating with node i.

Input

The first line of input gives the number of cases,N(1<=N<=100). N test case follow. In each test case, the first line is the number of the nodes M(1<=M<=18), then there are a grid by M*M describled the matrix.

Output

For each test case, output the maximum number of nodes that can communicate simultaneously.

Sample input 2 5 NYYYY YNNNN YNNNN YNNNN YNNNN 5 NYYYY YNNNN YNNNY YNNNY YNYYN

Smaple output 2 4

Hint

The first test case: all communications must occur with node 0,since node 0 can only communicate with 1 node at a time. The output value is 2.

The second test case: in this setup. We can let node 0 communicate with node1, and node 3 communicate with node 4.

Page 9 / Total 9