(软件学院)首届ACM程序设计竞赛.doc

第一题 字母旋转游戏

Description
给定两个整数M，N，生成一个M*N的矩阵，矩阵中元素取值为A至Z的26个字母中的一个，A在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过26时又从A开始填充。例如，当M=5，N=8时，矩阵中的内容如下：
A B C D E F G H

V W X Y Z A B I

U J K L M N C J

T I H G F E D K

S R Q P O N M L
Input
M为行数，N为列数，其中M，N都为大于0的整数。
Output
分行输出相应的结果
Sample Input
4 9
Sample Output
A B C D E F G H I
V W X Y Z A B C J
U J I H G F E D K
T S R Q P O N M L

第二题 小孩报数问题
Description
有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。
Input
第一行输入小孩的人数N（N<=64）
接下来每行输入一个小孩的名字(人名不超过15个字符)
最后一行输入W,S (W < N)，用逗号","间隔
Output
按人名输出小孩按顺序出列的顺序，每行输出一个人名
Sample Input
5
Xiaoming
Xiaohua
Xiaowang
Zhangsan
Lisi
2,3
Sample Output
Zhangsan
Xiaohua
Xiaoming
Xiaowang
Lisi

第三题 分割的种类
Description
排列组合问题中，分割是个有趣的问题。分割的意思，是把一个数字切成很多小部分之后，要保持总和不变。例如a+b+c=5, 而a,b,c都要是整数。则可能的情况是1+1+3，或是1+3+1或是1+2+2…等有很多个。现在为了简化问题，我们只想知道输入一个数字N,请问只用1,2,3三个数字来切，则共有几种不同的组合方式？请印出全部的组合。
例如N=5,则输出 5=1+1+1+1+1=1+1+1+2=1+1+3=1+2+2=2+3 ，共有5种可能。
若N=6，则输出6=1+1+1+1+1+1=1+1+1+1+2=1+1+1+3=1+1+2+2=1+2+3=2+2+2=3+3共有7种可能。
Input
每行一个样本，在那一行中，只有一个数字N，而字母的数量是1到15之间。
Output
每个样本，有很多行输出。每行代表一种可能，请印出全部可能的组合情形。而印出来的顺序可以与范例不同。但总数要相同。另外，每个样本之间用一个空白行隔开。
Sample Input
3
5
6
15
Sample Output
1+1+1
1+2
3

1+1+1+1+1
1+1+1+2
1+1+3
1+2+2
2+3

1+1+1+1+1+1
1+1+1+1+2
1+1+1+3
1+1+2+2
1+2+3
2+2+2
3+3

1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1+1+1+1+2
….
<中间省略>
….
1+2+2+2+2+3+3
1+2+3+3+3+3
2+2+2+2+2+2+3
2+2+2+3+3+3
3+3+3+3+3

第四题 二叉树
Description

如上图所示，由正整数1，2，3……组成了一颗二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。

比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。
Input
输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。
Output
对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
Sample Input
3 12
0 0
Sample Output
4
第五题 Subimage Recognition
Description
An image A is said to be a subimage of another image B if it is possible to remove some rows and/or columns of pixels from B so that the resulting image is identical to A. Figure 6 illustrates an example. Image A, shown in Figure 6(a), is a subimage of image B, shown in Figure 6(b), because the image resulting from the removal of the middle row and column of pixels from B is identical to A.

(a) Image A

(b) Image B
Figure 6: An example of a subimage
Given two black-and-white images A and B, determine whether A is a subimage of B.
Input
The input contains a single test case. The first line contains two integers r and c (1 ≤ r, c ≤ 20), the dimensions of A. The following r lines, each containing a string of length c, give an r × c 0-1 matrix representing the pixels of A. The next line contains two integers R and C (r ≤ R ≤ 20; c ≤ C ≤ 20), the dimensions of B. The following R lines, each containing a string of length C, give an R × C 0-1 matrix representing the pixels of B. A 0 indicates a white pixel; a 1 indicates a black pixel.
Output
If A is a subimage of B, print “Yes”; otherwise, print “No”.
Sample Input
2 2
11
10
3 3
101
000
100
Sample Output
Yes
第六题 Escort of Dr. Who How
Description
The notorious ringleader and cyber-criminal Derek Wu, better known as Dr. Who How, has been convicted for multiple abductions and cyber-frauds several minutes ago. He will soon be transferred from the court to the prison to serve a life sentence. Intelligence from undercover officers in Dr. Who How’s outlawed gang indicates a possible forcible rescue operation by gang members in the case that Dr. Who How is convicted. To ensure a successful escort, besides adopting enhanced security measures, the police force further desires to minimize the escort time—the time that the motorcade of escort has to spend between departure from the court and arrival at the prison.
The complex traffic condition in the city imposes complications on the police force’s escort effort. While the municipal government has agreed to temporarily shut down a few roads for exclusive police use, the shut-down time windows vary among roads and are generally narrow to avoid excessively disturbing the life of the citizens. The motorcade of escort must pass through any road entirely within its shut-down time window and not use any road that the municipal government has not agreed to shut down.
Given information about all roads available to the police force for the escort, determine the shortest escort time.
Input
The input contains a single test case. The first line contains four integers n, m, s and t (2 ≤ n ≤ 100; 0 ≤ m ≤ 1000; 1 ≤ s, t ≤ n; s ≠ t). There are n junctions, some pairs of which are connected by m roads. The court and the prison are located at the s-th and the t-th junctions, respectively. The next m lines each contain five integers x, y, b, e and c (1 ≤ x, y ≤ n; 0 ≤ b < e ≤ 104; 1 ≤ c ≤ 104), indicating that the directed lanes running from the x-th junction to the y-th junction of a road that takes the motorcade of escort c units of time to pass through will be shut down between time b and e. The earliest time when the motorcade can leave the court is time 0.
Output
If the escort is possible, print the shortest escort time; otherwise, print “Impossible”.
Sample Input
4 5 1 4
1 2 0 1 1
1 2 0 1 2
1 3 1 3 2
2 4 3 4 1
3 4 3 4 1
Sample Output
3
Hint
The sample is depicted in Figure 1. Each junction is represented by a numbered spot. Each road is represented by an arrow labeled with , its shut-down time window and pass-through time.

Figure 1: Depiction of the sample
The second road listed in the sample is virtually unusable for it takes the motorcade of escort longer time to pass through than it can stay available. The remaining four roads enable the following two escort routes:
1.
2.
(The label over an arrow indicates that the motorcade passes through the corresponding road between time s and t.) The first route takes four units of escort time, whereas the second takes three, which is the shortest possible.

第七题 George’s sticks
Description
George took sticks of the same length and cut them randomly until all parts became at most 20 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
Input consists of multiple problem instances. Each instance contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5

第八题 Magical e
Description
A simple mathematical formula for e is

where n is allowed to go to infinity. This can actually yield very accurate approximations of e using relatively small values of n.
Input
Input consists of m( 1<m<10) lines of integer numbers whose values
from 0 to m-1 by the order from little to large.
Output

Output the approximations of e generated by the above formula for the values of n from 0 to 9. The beginning of your output should appear similar to that shown below.

Sample Input
0
1
2
3
4
Output
n e
- -----------
0 1
1 2
2 2.5
3 2.666666667
4 2.708333333