当前位置：文档库 › 第三届ACM程序设计大赛试题new

第三届ACM程序设计大赛试题new

计算机工程学院

第三届ACM程序设计大赛试题

Problem A Bridge

Description

n people wish to cross a bridge at night. A group of at most two people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross.

Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time.

Input

The first line of input contains n, followed by n lines giving the crossing times for each of the people. There are not more than 1000 people and nobody takes more than 100 seconds to cross the bridge. Output

The first line of output must contain the total number of seconds required for all n people to cross the bridge. The following lines give a strategy for achieving this time. Each line contains either one or two integers, indicating which person or people form the next group to cross. (Each person is indicated by the crossing time specified in the input. Although many people may have the same crossing time the ambiguity is of no consequence.) Note that the crossings alternate directions, as it is necessary to return the flashlight so that more may cross. If more than one strategy yields the minimal time, any one will do.

Sample Input（Input file: pa.txt）

Sample Output

1 2

5 10

1 2

Problem B Lotto

Description

In the German Lotto you have to select 6 numbers from the set {1,2,...,49}. A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S = {1,2,3,5,8,13,21,34} there are 28 possible games: [1,2,3,5,8,13], [1,2,3,5,8,21],

[1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34].

Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S.

Input

The input will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending order. Input will be terminated by a value of zero (0) for k.

Output

For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.

Sample Input（Input file: pb.txt）

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 34

Sample Output

1 2 3 4 5 6

1 2 3 4 5 7

1 2 3 4 6 7

1 2 3 5 6 7

1 2 4 5 6 7

1 3 4 5 6 7

2 3 4 5 6 7

1 2 3 5 8 13

1 2 3 5 8 21

1 2 3 5 8 34

1 2 3 5 13 21

1 2 3 5 13 34

1 2 3 5 21 34

1 2 3 8 13 21

1 2 3 8 13 34

1 2 3 8 21 34

1 2 3 13 21 34

1 2 5 8 13 21

1 2 5 8 13 34

1 2 5 8 21 34

1 2 5 13 21 34

1 2 8 13 21 34

1 3 5 8 13 21

1 3 5 8 13 34

1 3 5 8 21 34

1 3 5 13 21 34

1 3 8 13 21 34

1 5 8 13 21 34

2 3 5 8 13 21

2 3 5 8 13 34

2 3 5 8 21 34

2 3 5 13 21 34

2 3 8 13 21 34

2 5 8 1

3 21 34

3 5 8 13 21 34

Problem C Encrypt

Chip and Dale have devised an encryption method to hide their (written) text messages. They first agree secretly on two numbers that will be used as the number of rows (R) and columns (C) in a matrix. The sender encodes an intermediate format using the following rules:

1. The text is formed with uppercase letters [A-Z] and .

2. Each text character will be represented by decimal values as follows:

= 0, A = 1, B = 2, C = 3, ..., Y = 25, Z = 26

The sender enters the 5 digit binary representation of the characters' values in a spiral pattern along the matrix as shown below. The matrix is padded out with zeroes (0) to fill the matrix completely. For example, if the text to encode is: "ACM" and R=4 and C=4, the matrix would be filled in as follows:

A = 00001, C = 00011, M = 01101 (one extra 0)

The bits in the matrix are then concatenated together in row major order and sent to the receiver. The example above would be encoded as: 0000110100101100

Input

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing R (1 ≤ R ≤ 20), a space, C (1 ≤ C ≤ 20), a

space, and a string of binary digits that represents the contents of the matrix (R * C binary digits). The binary digits are in row major order.

Output

For each dataset, you should generate one line of output with the following values: The dataset number as a decimal integer (start counting at one), a space, and the decoded text message. You should throw away any trailing spaces and/or partial characters found while decoding.

Sample Input（Input file: pc.txt）

4 4 ACM

5 2 HI

Sample Output

1 0000110100101100

2 0110000010

Problem D Connection

There are N cities in the country and M bidirectional roads between the cities. The government wants to build some new roads such that for any pair of cities there is at least one path between them. Now you have to find out the minimal amount of roads that have to build.

Input

The input may contain multiple test cases.

For each test case, the first line is two integers N (1<=N<=100) and M (1<=M<=N*N/2),

indicating the number of cities and the number of roads. Then the next M lines each contain two integers x and y (0<=x,y

N=M=0 indicates the end of input.

Output

For each test case, print the answer in a single li ne.

Sample Input（Input file: pd.txt）

5 2

0 1

2 3

Sample Output

Problem E Gridland

Background

For years, computer scientists have been trying to find efficient solutions to different computing problems. For some of them efficient algorithms are already available, these are the "easy" problems like sorting, evaluating a polynomial or finding the shortest path in a graph. For the "hard" ones only exponential-time algorithms are known. The traveling-salesman problem belongs to this latter group. Given a set of N towns and roads between these towns, the problem is to compute the shortest path allowing a salesman to visit each of the towns once and only once and return to the starting point.

Problem

The president of Gridland has hired you to design a program that calculates the length of the shortest traveling-salesman tour for the towns in the country. In Gridland, there is one town at each of the points of a rectangular grid. Roads run from every town in the directions North, Northwest, West, Southwest, South, Southeast, East, and Northeast, provided that there is a neighbouring town in that direction. The distance between neighbouring towns in directions North?CSouth or East?CWest is 1 unit. The length of the roads is measured by the Euclidean distance. For example, Figure 7 shows 2 ?? 3-Gridland, i.e., a rectangular grid of dimensions 2 by 3. In 2 ?? 3-Gridland, the shortest tour has length 6.

Figure 7: A traveling-salesman tour in 2 ?? 3-Gridland.

Input

The first line contains the number of scenarios.

For each scenario, the grid dimensions m and n will be given as two integer numbers in a single line, separated by a single blank, satisfying 1 < m < 50 and 1 < n < 50.

Output

The output for each scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. In the next line, print the length of the shortest traveling-salesman tour rounded to two decimal digits. The output for every scenario ends with a blank line.

Sample Input（Input file: pe.txt）

2 2

2 3

Sample Output

Scenario #1:

4.00

Scenario #2:

6.00

Problem F Digital Roots

Background

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.

Sample input（Input file: pf.txt）

Sample Output

Problem G Counting Numbers

Starting from a positive integer n (1<=n<=2001).On the left of the integer n ,you can place another integer m to form a new integer mn , where m must be less then or equal to half of the integer n ,If there is an integer k less then or equal to half of m, you can place integer k on the left of mn ,to form a new integer kmn,…,and so on .For Examole ,you can place 12 on the left of 30 to Form an integer 1230,and you can place 6 to the left of 1230 to form an integer 61230,…,and so on

For example , start from n=8.

you can place integer 1,2,3and 4 to the left of 8 to get the integers 18,28,38,48.

For number 18,you can not form a new integer using the procedure described as above.

For number28 and 38,you can form new integers 128 and 138.

For number 48 ,you can place 1 and 2 on the left of 48 to get new integers 148 and 248.

For number 248,you can place 1 on the left of it to get a new integer 1248.

In total, you can have the following 10 integers(includeing the integer you start with)

128

138

148

248

1248

Give an integer n ,find the number of integers you can get using the procedure described above.

Input

An integer n

Output

An integer witch represents the number of integer you can get.

Sample input: （Input file: pg.txt）

Sample Output:

Problem H Buy Low, Buy Lower

The advice to "buy low" is half the formula to success in the stock market. But to be considered a great investor you must also follow this problems' advice:

"Buy low, buy lower"

That is, each time you buy a stock, you must purchase more at a lower price than the previous time you bought it. The more times you buy at a lower price than before, the better! Your goal is to see how many times you can continue purchasing at ever lower prices.

You will be given the daily selling prices of a stock over a period of time. You can choose to buy stock on any of the days. Each time you choose to buy, the price must be lower than the previous time you bought stock. Write a program which identifies which days you should buy stock in order to maximize the number of times you buy.

By way of example, suppose on successive days stock is selling like this:

Day 1 2 3 4 5 6 7 8 9 10 11 12

Price 68 69 54 64 68 64 70 67 78 62 98 87

In the example above, the best investor (by this problem, anyway) can buy at most four times if they purchase at a lower price each time. One four day sequence (there might be others) of acceptable buys is:

Day 2 5 6 10

Price 69 68 64 62

PROGRAM NAME: buylow

Input

Line 1: N (1 <= N <= 5000), the number of days for which stock prices are available.

Line 2..etc: A series of N positive space-separated integers (which may require more than one line of data) that tell the price for that day. The integers will fit into 32 bits quite nicely.

Output

the length of the longest sequence of decreasing prices

Sample input: （Input file: ph.txt）

68 69 54 64 68 64 70 67 78 62 98 87

Sample Output:

注意事项：

1、数据从文件输入，标准输出，注意输入文件名题中已经给出。

2、Time Limit:1000MS Memory Limit:65536K

3、调试程序无警告、错误后提交。

4、注意选择正确题目、语言，慎重提交。

参考程序（C语言）

#include

main()

{

int a,b;

freopen("in.txt","r",stdin); //输入重定向，输入数据将从in.txt文件中读取while(scanf("%d %d",&a,&b)!=EOF)

printf("%d\n",a+b);

fclose(stdin);//关闭文件

}

参考程序（C++语言）

#include

using namespace std;

int main()

{

int a,b;

freopen("in.txt","r",stdin); //输入重定向，输入数据将从in.txt文件中读取while(cin>>a>>b)

cout<

fclose(stdin);//关闭文件

return 0;

}