计算机学院ACM设计大赛初赛试题.doc

ACM程序设计竞赛初赛试题问题一： 给定一个N位的二进制串b1 b2 bN-1 bN 将该串做旋转，即将b1移到bN后面，得到一个新的二进制串：b2 bN-1 bN b1 对新的二进制串再做旋转，得二进制串b3 b4 bN-1 bN b1 b2 重复旋转操作操作，可得N个二进制串，对这N个串排序，可得一个N*N的矩阵 问：给定这种矩阵的最后一列，求出矩阵的第一行。对于上面的例子，给出 1 0 0 1 0，要你的程序输出 0 0 0 1 1。问题二： 某地的交通网由路口和公路构成： 两个路口之间最多有一条公路，公路两个方向的行驶时间相同。每个路口有一盏信号灯，有B/P两种颜色状态。每盏信号灯以它独有的周期进行颜色交替。 车辆的行驶规则： 当且仅当某个时刻一条路两端的信号灯颜色相同时，车辆可以从一端出发驶向另一端。车辆可以在路口等候，路口处等候的车辆没有限制。 任务：给定交通网的结构以及信号灯的初始状态和变化周期，求某两点间最快到达的路径。问题三：回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数，并输出任意给定的字符串的回文词。比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。注：此问题区分大小写。问题四： 1）将一个圆盘分成N（N = 6）个扇形，往每个扇形内放入一个整数（这些整数都要大于给定的K值）。2）然后从这些整数中选择任意多个相邻的整数（可以选一个，也可以选多个），得到它们的和。3）将2）中所得的和排成从M开始的一组连续整数，M, M+1, ,J4）此题的任务是：往扇形中添加合适的整数，使得J 值最大。示例：问题五： 给定n个车站，找两个车站做总站，每个车站必须连到其中的一个总站，两个车站不能直接相连，必须通过总站连接。求使得任意两个车站之间的距离最短的方案，输出该方案下两车站间的最大距离。在平面上给出n个点，从中选择两个点连在一起，并找出一种把其他的点连到这两个点上的方案，使得任意两点间的最长路径距离最短。车站数目N：2=N=500。问题六：司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 问题七：l 背景古斯迪尔文明曾在约10亿年前在地球上辉煌一时，尤其在历法、数学、天文等方面的发展水平已经超过现代。在古城的众多庙宇中，考古人员都发现了一种奇特的建筑，该建筑包含一排独立的房间。1 2 3 4 5 6 7 8 9以下是一个规模较小的建筑的内部结构，包括9个房间：转盘 在每个房间的中央，挂有一个转盘，每个转盘分为6个格子，每个格子写着一个1到9的数字。转盘可以逆时针转动。转盘的红色标记始终指向上方的格子。每个房间的转盘都不相同。CC考古工作室近日成功地破译了当时的文字，对进一步研究古斯迪尔文明作出了重要贡献。首先，研究人员翻译了当时的宗教书籍，得知了建筑的用途。原来每个寺院都要在建成以后每隔若干年举行一次大型的庆典。由于“天机不可泄漏”，寺院方面并不直接说明庆典的日期，而是采用“暗示”的方法。奇特的建筑就是为了确定庆典的日期而专门建造的。房间从左到右编号为1，2，3，n，同时寺院有n个祭司也从1到n编号，这些祭司每年到房间中祈祷一次。建寺那年祭司和自己编号相同的房间祈祷。同时，转盘上红色标记指示的格子的数字就是该祭司第二年祈祷的房间编号。在祭司祈祷完毕以后，将转盘逆时针旋转一格。转盘的设计使得在每年祈祷时，每个房间只有一个祭司。从建寺以后，当某一年祈祷时，每个祭司的编号都和祈祷房间的编号相同时，就是举行庆典的日期。实际上，每隔若干年，就会有一次庆典。l 任务作为CC考古工作室的首席软件顾问，你负责编程求出第一次举行庆典的确切日期。l 输入文件第一行是两个整数n，p，n表示房间的数目（也就是祭司的数目），p表示转盘包含的格子的数目。(0 n, p = 200)以下有n行，每行p个整数，表示每个房间转盘的格子上的数字。每行第一个数表示寺院建立时红色标记指向的数字，以下的数字按照顺时针方向给出。l 输出仅一行，表示第一次举行庆典是在建寺以后多少年。如果永远不会出现符合条件的情况或者第一次符合条件的年份超过109（那时古斯迪尔文明已经衰落了），则输出No one knows.Sample Input 1Sample Input 210 1761082415396 32 6 31 1 14 4 66 3 53 2 25 5 4Sample Output 2Sample Output 23018问题八： 迈克在一个养猪场工作，场里有M个猪圈，每个猪圈都上了锁由于迈克没有钥匙，所以他不能打开任何一个猪圈。 顾客一个接一个来到养猪场，每个顾客有一些猪圈的钥匙，而且他们要买一些猪。所有在某天要到养猪场的顾客，他们的信息是要提前让迈克知道的。 这些信息包括顾客所拥有的钥匙、要购买的数量，这样对迈克很有好处：他可以安排销售计划以便卖出最大的数目。 当每个顾客到来时，他将那些他拥有钥匙的猪圈全部打开，迈克从这些猪圈中挑出一些猪卖给他们。 如果迈克愿意，迈克可以重新分配这些被打开的猪圈中的猪，猪圈再次被锁上。注意：猪圈可容纳的猪的数量没有限制 第一行是两个整数：M和N（1M1000，1N100） M是猪圈的数目，N是顾客的数目 第二行是M个整数，为每个猪圈中初始猪的数目，范围是0，1000接下来的N行是顾客的信息，第i个顾客的信息保存在第i+2行顾客信息：A K1 K2 KA BA为拥有钥匙的数目，Kj表示拥有第Kj个猪圈的钥匙B为该顾客想买的猪的数目A，B均可为0输出：能够卖掉的猪的最大数目问题九：已知一个n元高次方程：其中且方程中所有数均为整数。任务：求方程的整数解的个数，给出方程的元数、取值的上限、以及系数和指数。约束条件：n 6, 1M150方程的整数解的个数小于231问题十： 条形码（Bar Code）由交替的黑白条并列构成。最左边的总是黑色条。 用x个1表示宽度为x的黑色条，y个0表示宽度为y的白色条，可以得到条形码的二进制编码。 BC (n, k, m)定义为满足以下条件的条形码的集合： 总宽度为n；黑白条总数为k；每根黑色条或白色条的宽度不超过m。例：右图所示的条形码编码为1001110；属于BC (7, 4, 3)，不属于BC (7, 4, 2)。问题十一：Description Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. Write a program that will count how many pairs which are valid for a given tree. Input The input contains several test cases. The first line of each test case contains two integers n, k. (n=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. The last test case is followed by two zeros. Output For each test case output the answer on a single line.Sample Input 5 41 2 31 3 11 4 23 5 10 0Sample Output 8问题十二：Description There is a square wall which is made of n*n small square bricks. Some bricks are white while some bricks are yellow. Bob is a painter and he wants to paint all the bricks yellow. But there is something wrong with Bobs brush. Once he uses this brush to paint brick (i, j), the bricks at (i, j), (i-1, j), (i+1, j), (i, j-1) and (i, j+1) all change their color. Your task is to find the minimum number of bricks Bob should paint in order to make all the bricks yellow. Input The first line contains a single integer t (1 = t = 20) that indicates the number of test cases. Then follow the t cases. Each test case begins with a line contains an integer n (1 = n = 15), representing the size of wall. The next n lines represent the original wall. Each line contains n characters. The j-th character of the i-th line figures out the color of brick at position (i, j). We use a w to express a white brick while a y to express a yellow brick.Output For each case, output a line contains the minimum number of bricks Bob should paint. If Bob cant paint all the bricks yellow, print inf.Sample Input 23yyyyyyyyy5wwwwwwwwwwwwwwwwwwwwwwwwwSample Output 015问题十三：Description There is an old stone game, played on an arbitrary general tree T. The goal is to put one stone on the root of T observing the following rules: 1. At the beginning of the game, the player picks K stones and puts them all in one bucket. 2. At each step of the game, the player can pick one stone from the bucket and put it on any empty leaf. 3. When all of the r immediate children of a node p each has one stone, the player may remove all of these r stones, and put one of the stones on p. The other r - 1 stones are put back into the bucket, and can be used in the later steps of the game.The player wins the game if by following the above rules, he succeeds to put one stone on the root of the tree. You are to write a program to determine the least number of stones to be picked at the beginning of the game (K), so that the player can win the game on the given input tree. Input The input describes several trees. The first line of this file is M, the number of trees (1 = M = 10). Description of these M trees comes next in the file. Each tree has N 200 nodes, labeled 1, 2, . N, and each node can have any possible number of children. Root has label 1. Description of each tree starts with N in a separate line. The following N lines describe the children of all nodes in order of their labels. Each line starts with a number p (1 = p = N, the label of one of the nodes), r the number of the immediate children of p, and then the labels of these r children.Output One line for each input tree showing the minimum number of stones to be picked in step 1 above, in order to win the game on that input tree.Sample Input 271 2 2 32 2 5 43 2 6 74 05 06 07 0121 3 2 3 42 03 2 5 64 3 7 8 95 3 10 11 126 07 08 09 010 011 012 0Sample Output 34问题十四：Description A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.Input The first line of the input contains a single integer T (1 = T = 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river. There wont be more than 1000 people and nobody takes more than 100 seconds to cross.Output For each test case, print a line containing the total number of seconds required for all the N people to cross the river.Sample Input 141 2 5 10Sample Output 17问题十五：Description People in Silverland use coins.They have coins of value A1,A2,A3.An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didnt know the exact price of the watch. You are to write a program which reads n,m,A1,A2,A3.An and C1,C2,C3.Cn corresponding to the number of Tonys coins of value A1,A2,A3.An then calculate how many prices(form 1 to m) Tony can pay use these coins. Input The input contains several test cases. The first line of each test case contains two integers n(1=n=100),m(m=100000).The second line contains 2n integers, denoting A1,A2,A3.An,C1,C2,C3.Cn (1=Ai=100000,1=Ci=1000). The last test case is followed by two zeros.Output For each test case output the answer on a single line.Sample Input 3 101 2 4 2 1 12 51 4 2 10 0Sample Output 84问题十六：Description Flavius Josephus and 40 fellow rebels were trapped by the Romans. His companions preferred suicide to surrender, so they decided to form a circle and to kill every third person and to proceed around the circle until no one was left. Josephus was not excited by the idea of killing himself, so he calculated the position to be the last man standing (and then he did not commit suicide since nobody could watch). We will consider a variant of this game where every second person leaves. And of course there will be more than 41 persons, for we now have computers. You have to calculate the safe position. Be careful because we might apply your program to calculate the winner of this contest! Input The input contains several test cases. Each specifies a number n, denoting the number of persons participating in the game. To make things more difficult, it always has the format xyez with the following semantics: when n is written down in decimal notation, its first digit is x, its second digit is y, and then follow z zeros. Whereas 0=x,y=9, the number of zeros is 0=z0. The last test case is followed by the string 00e0. Output For each test case generate a line containing the position of the person who survives. Assume that the participants have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2. For example, if there are 5 persons in the circle, counting proceeds as 2, 4, 1, 5 and person 3 is staying alive.Sample Input 05e001e142e066e600e0Sample Output 352164891137问题十七：Description Since the days of Peter Stuyvesant and Abel Tasman, Dutch merchants have been traveling all over the world to buy and sell goods. Once there was some trade on Verweggistan, but it ended after a short time. After reading this story you will understand why. At that time Verweggistan was quite popular, because it was the only place in the world where people knew how to make a prul. The end of the trade on Verweggistan meant the end of the trade in pruls (or prullen, as the Dutch plural said), and very few people nowadays know what a prul actually is. Pruls were manufactured in workyards. Whenever a prul was finished it was packed in a box, which was then placed on top of the pile of previously produced pruls. On the side of each box the price was written. The price depended on the time it took to manufacture the prul. If all went well, a prul would cost one or two florins, but on a bad day the price could easily rise to 15 florins or more. This had nothing to do with quality; all pruls had the same value. In those days pruls sold for 10 florins each in Holland. Transportation costs were negligible since the pruls were taken as extra on ships that would sail anyway. When a Dutch merchant went to Verweggistan, he had a clear purpose: buy pruls, sell them in Holland, and maximize his profits. Unfortunately, the Verweggistan way of trading pruls made this more complicated than one would think. One would expect that merchants would simply buy the cheapest pruls, and the pruls that cost more than 10 florins would remain unsold. Unfortunately, all workyards on Verweggistan sold their pruls in a particular order. The box on top of the pile was sold first, then the second one from the top, and so on. So even if the fifth box from the top was the cheapest one, a merchant would have to buy the other four boxes above to obtain it. As you can imagine, this made it quite difficult for the merchants to maximize their profits by buying the right set of pruls. Not having computers to help with optimization, they quickly lost interest in trading pruls at all. In this problem, you are given the description of several workyard piles. You have to calculate the maximum profit a merchant can obtain by buying pruls from the piles according to the restrictions given above. In addition, you have to determine the number of pruls he has to buy to achieve this profit. Input The input describes several test cases. The first line of input for each test case contains a single integer w, the number of workyards in the test case (1 = w = 50). This is followed by w lines, each describing a pile of pruls. The first number in each line is the number b of boxes in the pile (0 = b = 20). Following it are b positive integers, indicating the prices (in florins) of the pruls in the stack, given from top to bottom. The input is terminated by a description starting with w = 0. This description should not be processed. Output For each test case, print the case number (1, 2, .). Then print two lines, the first containing the maximum profit the merchant can achieve. The second line should specify the number of pruls the merchant has to buy to obtain this profit. If this number is not uniquely determined, print the possible values in increasing order. If there are more than ten possible values, print only the 10 smallest. Display a blank line between test cases. Sample Input 16 12 3 10 7 16 525 7 3 11 9 109 1 2 3 4 10 16 10 4 160Sample Output Workyards 1Maximum profit is 8.Number of pruls to buy: 4Workyards 2Maximum profit is 40.Number of pruls to buy: 6 7 8 9 10 12 13问题十八：Description To enable homebuyers to estimate the cost of flood insurance, a real-estate firm provides clients with the elevation of each 10-meter by 10-meter square of land in regions where homes may be purchased. Water from rain, melting snow, and burst water mains will collect first in those squares with the lowest elevations, since water from squares of higher elevation will run downhill. For simplicity, we also assume that storm sewers enable water from high-elevation squares in valleys (completely enclosed by still higher elevation squares) to drain to lower elevation squares, and that water will not be absorbed by the land. From weather data archives, we know the typical volume of water that collects in a region. As prospective homebuyers, we wish to know the elevation of the water after it has collected in low-lying squares, and also the percentage of the regions area that is completely submerged (that is, the percentage of 10-meter squares whose elevation is strictly less than the water level). You are to write the program that provides these results. Input The input consists of a sequence of region descriptions. Each begins with a pair of integers, m and n, each less than 30, giving the dimensions of the rectangular region in 10-meter units. Immediately following are m lines of n integers giving the elevations of the squares in row-major order. Elevations are given in meters, with positive and negative numbers representing elevations above and below sea level, respectively. The final value in each region description is an integer that indicates the number of cubic meters of water that will collect in the region. A pair of zeroes follows the description of the last region. Output For each region, display the region number (1, 2, .), the water level (in meters above or below sea level) and the percentage of the regions area under water, each on a separate line. The water level and percentage of the regions area under water are to be displayed accurate to two fractional digits. Follow the output for each region with a blank line. Sample Input 3 325 37 4551 12 3494 83 27100000 0Sample Output Region 1Water level is 46.67 meters.66.67 percent of the region is under water.问题十九：Eva has a balance with 20 poises. The weights of the poises are 1,3, 9, 27,.,319. Eva asserts that she has a way to measure anyobject whose weight is an integer from 1 to (320-1)/2. Assumingthat Eva has placed a