(软件学院)首届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 LInputM为行数，N为列数，其中M，N都为大于0的整数。Output分行输出相应的结果Sample Input4 9Sample 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 Input5XiaomingXiaohuaXiaowangZhangsanLisi2,3Sample OutputZhangsanXiaohuaXiaomingXiaowangLisi第三题 分割的种类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 Input35615Sample Output1+1+11+231+1+1+1+11+1+1+21+1+31+2+22+31+1+1+1+1+11+1+1+1+21+1+1+31+1+2+21+2+32+2+23+31+1+1+1+1+1+1+1+1+1+1+1+1+1+11+1+1+1+1+1+1+1+1+1+1+1+1+2.1+2+2+2+2+3+31+2+3+3+3+32+2+2+2+2+2+32+2+2+3+3+33+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 0Sample Output4第五题 Subimage RecognitionDescriptionAn 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 BFigure 6: An example of a subimageGiven two black-and-white images A and B, determine whether A is a subimage of B.InputThe 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.OutputIf A is a subimage of B, print “Yes”; otherwise, print “No”.Sample Input2 211103 3101000100Sample OutputYes第六题 Escort of Dr. Who HowDescriptionThe 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 Hows 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 timethe 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 forces 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.InputThe 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.OutputIf the escort is possible, print the shortest escort time; otherwise, print “Impossible”.Sample Input4 5 1 41 2 0 1 11 2 0 1 21 3 1 3 22 4 3 4 13 4 3 4 1Sample Output3HintThe 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 sampleThe 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.第七题 Georges sticksDescriptionGeorge 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. InputInput 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 co