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

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 2 3

ACM

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）

24 39 0

Sample Output

6 3

ACM

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) 8 18 28 38 48 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）

8

Sample Output:

10

ACM

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）

12

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

Sample Output:

4

ACM

注意事项：

1、 数据从文件输入，标准输出，注意输入文件名题中已经给出。 2、 Time Limit:1000MS Memory Limit:65536K 3、 调试程序无警告、错误后提交。

4、 注意选择正确题目、语言，慎重提交。 参考程序（C语言） #include <stdio.h> 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 <iostream> using namespace std; int main() {

int a,b;

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

cout<<a+b<<endl; // 注意使用endl fclose(stdin);//关闭文件 return 0; }