ACM程序设计试题

1、ACM程序设计试题1. 平方数 给出包含M个数字的列表，和列表中所有数字的所有质因数。求出最长的子列表，使得子列表中所有数字的乘积是一个完全平方数。b5E2RGbC输入 输入文件包含多组测试数据。第一行包含两个整数N , M ( 1 = N = 30 , 1 = M = 30000 ). N 是质因数的个数。接下来一行有N个整数，给出所有的质因数。然后一行包含M个整数，给出列表。p1EanqFD输入文件结束于N = M = 0.输出 对于每组数据，输出最长子列表的两个位置坐标l r。l是该子列表在列表中的起始位置，r是结束位置。如果多种情况都满足子列表长度最大，输出l最小的一个。如果不存在这样

2、的子列表输出“None”。DXDiTa9E样例输入3 42 3 54 9 25 63 42 3 56 6 3 30 0样例输出1 31 42.母牛生小牛Problem设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？Input本题有多组数据。每组数据只有一个整数N，独占一行。(1N50)Output对每组数据，输出一个整数（独占一行）表示第N年时母牛的数量Sample Input14520Sample Output1238723.死亡迷宫背景很久以前，迷宫里住着一个恶魔。一天，我们伟大的英雄Andy无意中踏入了这个迷宫。不幸的是，他被困在这个迷宫当中了。恶魔在迷宫中

3、召唤出了许多怪物，想要阻止Andy逃脱。在迷宫中，Andy遇到一个一位巫师。他给了Andy迷宫的地图，并告诉他迷宫的入口很快会关闭。Andy必须以非常快的速度到达入口，并且有足够的力气推开挡在入口的岩石。于是，Andy带着地图一路向着出口走去RTCrpUDG问题给出Andy和各怪物的能量, 攻击力, 防御力，和迷宫的地图，请你计算一下 能量/耗时 的最大值。当Andy走到有怪物的地方时，Andy会先进行攻击，然后怪物攻击，然后Andy当一方的能量小于等于0时攻击停止，并且小于等于0的一方死亡。攻击时，每次对方损耗的能量为己方的攻击力减去对方的防御力。5PCzVD7H当Andy走到标有A,B,C

4、的地方时，Andy的相应属性会得到增加。对应关系如下：A 能量 + PB 攻击力 + QC 防御力 + R如果耗时超过100，那么门将永远也打不开了，我们的Andy也就永远的困在了这个暗无天日的迷宫之中输入标准输入包含多组数据。每组数据的第一行有六个整数W (1 = W = 20), H (1 = H = 20), P (1 = P = 10), Q (1= Q = 10), R (1 = R = 10), M (0 = M = 5). 迷宫是由一个W*H的矩形区域构成。M表示怪物的数量。Andy每个单位时间可以移动到相邻的4个格中，当然，必须得保证目标格在矩形区域中。默认的起始时间是0。与怪

5、物战斗不会花费额外的时间。jLBHrnAI其后H行每行严格包含W个字符。用如下的各字符表示这个迷宫的地图：#表示一堵墙（Andy是不会穿墙术的）. Marks an empty space, into which you can move.表示一块空地。xHAQX74JS表示Andy的初始位置。E表示迷宫的入口。0表示各怪物。A表示属性增加地点。（使用次数仅限于一次）其后一行有三个整数，表示Andy的能量，攻击力，和防御力。其后M行，每行有四个整数，表示怪物的编号，和这个怪物的各属性。输出对于每组输入数据，输出 能量/耗时 的最大值，并保留4位小数。如果Andy不能到达出口，输出“imposs

6、ible”。数据之间无空行。LDAYtRyK样例输入6 17 7 5 4 3#E.#.#A#.#.0.#.#B#1#2#.S.C#100 59 100 23 48 01 65 41 02 20 27 0样例输出3.70374.取石子游戏Description有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。Zzz6ZB2LInput输入包含若干行，表示

7、若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。dvzfvkwMOutput输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。Sample Input2 18 44 7Sample Output0105.猪的安家Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。这回Andy建造了5个猪圈，但是仍

8、然有1头猪没有地方去，然后Andy又建造了7个猪圈，但是还有2头没有地方去。Andy都快疯了。你对这个事情感兴趣起来，你想通过Andy建造猪圈的过程，知道Andy家至少养了多少头猪。rqyn14ZN输入输入包含多组测试数据。每组数据第一行包含一个整数n (n = 10) Andy建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi = ai = 1000), 表示Andy建立了ai个猪圈，有bi头猪没有去处。你可以假定(ai, aj) = 1.EmxvxOtO输出输出包含一个正整数，即为Andy家至少养猪的数目。样例输入33 15 17 2样例输出166.猫捉老鼠一只猫和一只老鼠在10

9、*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。SixE2yXP老鼠在迷宫中按照一种固定的方式行走：每个时刻，老鼠都向它所面对的方向前进一格，这需要花费秒时间。如果前方是一个障碍或者是迷宫的边界，它将花秒的时间按顺时针方向转90度。6ewMyirQ为了抓到老鼠，这只猫决定也按照与老鼠相同的行走方式行进。猫和老鼠在每个单位时间内是同时行动的。因此，如果猫和老鼠在行进过程中“擦肩而过”，猫是无法捉到老鼠的。只有当猫和老鼠同时

10、到达一个相同的格子时，猫才能捉住老鼠。kavU42VR初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。你的任务是编一个程序，求出猫捉到老鼠的所花时间。输入输出格式输入数据的第一行n，表示输入数据的组数。每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。y6v3ALoS每组输入数据之后均有一个空行作为间隔。对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。样例输入1*.*.*.*.*.*.c.*.*.*.m.*.*.*.*.*.样例输出497.炮兵阵地Description司令部

11、的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：M2ub6vST如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。0YujCfmU现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即

12、任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。eUts8ZQVInput第一行包含两个由空格分割开的正整数，分别表示N和M；接下来的N行，每一行含有连续的M个字符(P或者H)，中间没有空格。按顺序表示地图中每一行的数据。N = 100；M = 10。sQsAEJkWOutput仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。Sample Input5 4PHPPPPHHPPPPPHPPPHHPSample Output68.圣诞岛的旅行ProblemAngel最近无聊，去了圣诞岛(CX *_*)，他喜欢无目的的乱逛，当然，他不会轻易

13、地回头。Angel想去广场，那么，他什么时候才能到呢？你已经得到了CX的地图，地图上有N(N = 100)个交叉路口，交叉路口之间有马路相连接(不超过1000条马路)。因为CX的人遵循奇怪的规则，道路都是单向的，不同的道路之间有一定的距离，我们假设Angel所在的地点为点1，广场所在点为N。假设Angel走一单位距离需要一单位时间。问Angel最早和最迟什么时候到达广场？GMsIasNXInput本题有多组数据，第一行N, M，M是边的数量以后M行，每行3个整数X, Y, Weight，代表一条从X城市到Y城市，长度为Wweight的边。TIrRGchYOutput每组数据，第一行是最少时间，

14、第二行是最迟时间，要是可怜的Angel可能永远到不了广场，输出一行Never。7EqZcWLZSample Input5 51 2 11 4 102 3 13 4 14 5 1Sample Output4119.采药【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大

15、。”lzq7IGf0如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in的第一行有两个整数T（1 = T = 1000）和M（1 = M = 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。zvpgeqJ1【输出文件】输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。NrpoJac3【样例输入】70 371 10069 11 2【样例输出】3【数据规模】对于30%的数据，M =

16、10；对于全部的数据，M = 100。10.国家利益Background没有永远的朋友，也没有永远的敌人，国家的行为取决于国家利益，国家的地位取决于国家实力Problem伊拉克战争结束后.N个国家正在联合国开会商讨如何分配伊拉克的M块油田N个国家按国家实力编号1，2，3.N，1号国家实力最强，第一个发言，N号最后一个发言，依次类推发言国家会提出一个分配方案，所有有表决权的国家进行表决（包括发言国家自己），如果50%或以上同意此方案，则会议结束，按照此国的方案分配油田，否则该国丧失表决权，下个国家重复上述过程那么第一个国家提出怎样的方案才能使本国利益最大化？Hint每个国家分得的油田都是整数，不

17、会出现几个国家共同拥有一块油田每个国家都不希望别人的方案通过，但是每个国家都按照本国利益投票，比如1号国家提出一个方案， X号国家分Y油田，X号国家会进行比较， 如果该方案被否决，那么下次2号提出的方案X号国家分Z油田，而Z Y，那么X号国家会赞成1号的方案， 否则反对1nowfTG4Input每行包括2个整数N，M，（N,M = 108）Output每行包括1个整数，1号国家能获得的最多油田数Sample Input7 100Sample Output9711.防御导弹Problem某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到

18、任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。fjnFLDa5Input最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000的正整数）Output两个整数M和N。表示：这套系统最多能拦截 M 枚导弹，如果要拦截所有导弹最少要配备 N 套这种导弹系统。tfnNhnE6Sample Input300 250 275 252 200 138 245Sample Output5 212.技能树Problem玩过Diablo的人对技能树一定是很熟悉的。一颗技能树的每个

19、结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。HbmVN777只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是V7l4jRB8需要耗费技能点数的。有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为83lcPA59效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。Input该题有多组测试数据。每组测试数据第一行是一个整数n（1=n=20）,表示所有不同技能的总数。接下来依次给出n个不同技能的详细情况。每个技能描述包括5行。第一行

20、是该技能的名称。第2行是该技能在技能树中父技能的名称，名称为None则表示该技能不需要任何的先修技能便能学习。第3行是一个整数L（1=L=20），表示这项技能所能拥有的最高级别。第4行共有L个整数，其中第I个整数表示从地I-1级升到第I级所需要的技能点数（0级表示没有学习过）。第5行包括L个整数，其中第I个整数表示从第I-1级升级到第I级的效果评分，分数不超过20。在技能描述之后，共有两行，第1行是一个整数P，表示目前所拥有的技能点数。接下来1行是N个整数，依次表示角色当前习得的技能级别，0表示还未学习。这里不会出现非法情况。Output每组测试数据只需输出最佳分配方案所得的分数总和。Samp

21、le Input3Freezing ArrowIce Arrow33 3 315 4 6Ice ArrowCold Arrow24 310 17Cold ArrowNone33 3 215 5 2100 0 1Sample Output4213.砝码问题Problem有一组砝码，重量互不相等，分别为m1、m2、m3mn；它们可取的最大数量分别为x1、x2、x3xn。mZkklkza现要用这些砝码去称物体的重量,问能称出多少种不同的重量。Input第一行为一整数t,表示有t组测试数据。每组测试数据第一行一个整数n（n=10），表示有多种不同的砝码；第二行n个整数（中间用空格分隔），m1、m2、m

22、3mn，分别表示n个砝码的重量；（1=mi=20）AVktR43b第三行n个整数（中间用空格分隔），x1、x2、x3xn，分别表示n个砝码可取的最大数量。（1=xi=20）ORjBnOwcOutput每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数。注：包括0。Sample Input121 22 1Sample Output514.数列极差问题在黑板上写了N个正整数组成的一个数列，进行如下操作： 每次擦去其中的两个数a和b，然后在数列中加入一个数ab1，如此下去直至黑板上 剩下一个数，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min， 则该数列的极差定

23、义为Mmaxmin。2MiJTy0d请你编程，对于给定的数列，计算极差。输入输入包含多个测试集。每个测试集的第一个数N表示 正整数序列长度（0N50000），随后是N个正整数。N为0表示输入结束。gIiSpiue输出每个结果一行输入样例31230输出样例215.Number TriangleConsider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top

24、and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.uEh0U1Yf7 3 88 1 02 7 4 44 5 2 6 5In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.IAg9qLsgInputThere are multiple test cases.The first line of ea

25、ch test case contains R (1 = R = 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.WwghWvVhOutputPrint a single line containing the largest sum using the traversal specified

26、 for each test case.asfpsfpiSample Input573 88 1 02 7 4 44 5 2 6 5Sample Output3016.救援行动ProblemAngel被传说中神秘的邪恶的Moligpy人抓住了！他被关在一个迷宫中。迷宫的长、宽不超过200。迷宫中有不可以越过的墙以及监狱的看守。Angel的朋友带了一些救援队来到了迷宫中。他们的任务是：接近Angel。我们假设接近Angel就是到达Angel所在的位置。ooeyYZTj假设移动需要1单位时间，杀死一个看守也需要1单位时间。到达一个格子以后，如果该格子有看守，则一定要杀死（否则会死BkeGuInk的

27、很难看的只见那个看守开了9倍狙镜）。交给你的任务是，最少要多少单位时间，才能到达Angel所在的地方？PgdO0sRl（只能向上、下、左、右4个方向移动）Input该题含有多组测试数据。每组测试数据第一行二个整数n，m。表示迷宫的大小为n*m。以后n行，每行m个时字符。其中“#”代表墙，“.”表示可以移动，“x”表示看守，“a”表示Angel，“r”表示救援队伍。3cdXwckm字母均为小写。Output一行，代表救出Angel的最短时间。如果救援小组永远不能达到Angel处，则输出“Poor ANGEL has to stay in the prison all his life.”h8c5

28、2WOnSample Input7 8#.#.#.a#.r.#.#x.#.#.#.#.#.Sample Output1317.幻方矩阵Problem description幻方是一种很有意思的数字矩阵，在很早著名的九宫八卦阵就与幻方有关。幻方的定义为：1 到 N*N 的整数填入N*N的方格中，每行和每列以及对角线的数字之和必须是相等的。你作为八卦公司的顶级程序员，现在需要你解决一个问题，将任意奇数阶的幻方找出来。Input输入包括多个测试集，每行为一个正奇数N(1 = N 1000)，0作为输入的结束且不需要处理。Output对于输入的每一个N， 输出一个它所对应的N阶幻方，如果存在多个，任意

29、一个即可。每个幻方为N*N的矩阵，对于每个幻方，每行输出幻方的一行，每行中的数字之间用一个或多个空格分开。不同的幻方之间用一个空行分开。v4bdyGioSample Input130Sample Output14 9 23 5 78 1 618.整数划分问题整数划分是一个经典的问题。希望这道题会对你的组合数学的解题能力有所帮助。Input每组输入是两个整数n和k。(1 = n = 50, 1 = k = n)Output对于每组输入，请输出六行。第一行： 将n划分成若干正整数之和的划分数。第二行： 将n划分成k个正整数之和的划分数。第三行： 将n划分成最大数不超过k的划分数。第四行： 将n划分

30、成若干奇正整数之和的划分数。第五行： 将n划分成若干不同整数之和的划分数。第六行： 打印一个空行。Sample Input5 2Sample Output72333Hint:1、将5划分成若干正整数之和的划分为： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1J0bm4qMp2、将5划分成2个正整数之和的划分为： 3+2, 4+13、将5划分成最大数不超过2的划分为： 1+1+1+1+1, 1+1+1+2, 1+2+24、将5划分成若干奇正整数之和的划分为： 5, 1+1+3, 1+1+1+1+15、将5划分成若干不同整数之和的划分为： 5, 1+4

31、, 2+319.邮递员的烦恼Problem邮递员每天的任务是把邮件送到各家各户.日子长了,邮递员就会想,我每天是不是跑了很多的冤枉路呢?能不能找到一条最短的路XVauA9gr让我尽快的完成任务.这个问题困扰了他很久很久.最后他决定找一个程序员来解决这个问题.邮递员所在的城市共有m调东西向的马路和n调南北向的马路.这m+n条马路把整个城市分成了(m-1)*(n-1)个街区.每个街区长bR9C6TJs150米,宽120米.每一段马路上隔10米有一个门牌号.门牌号从1开始,由东向西,由北向南一次增加.所有奇数门牌号一律位于北侧pN9LBDdt或者东侧，偶数的门牌一律位于南侧或者西侧。因此每一段东西向

32、马路上共有28个门牌号码，每一段南北向的马路上共有22个门DJ8T7nHu牌号码。但是在环城的马路上是没有奇数号码或是偶数号码的门牌。见下图:每条马路都有一个编号，用H表示东西向，V表示南北方向，后面跟一个数表示由东向西数或者由北向南数第几条马路。譬如H1表QF81D7bv示最北边的东西向的马路，V2表示由东向西第二条南北向的马路。一个地址可以用马路编号+门牌号表示。邮递员每天要送信4B7a9QFw到许多不同的地址。由于他骑的是自行车，因此可以在马路上做U字形转弯。现在告诉你所有要送达的地址以及邮局的所有地址，请你为他规划一条最短的路线，使得他可以从邮局出发，把所有的邮件送出ix6iFA8x去

33、以后再回到邮局，马路的宽度忽略不计。Input该题含有多组测试数据。每组测试数据第一行是三个整数m,n,L(2=m,n=10,0=L=17)依次表示城市中东西向,南北向马路条数和邮递员要送达的不同地址数。wt6qbkCy接下来L行每行是一个地址，马路编号和门牌号之间用一个空格分隔。最后一行是邮局的地址。所有地址都保证是合法的且没有任何两个相同。Output输出的格式说明Sample Input5 5 3V3 32V5 41H5 51H2 61Sample Output138020.字符串的距离Problem设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符

34、串X为“abcbcd”，则字符串“abcbcd”，“abcbcd”和“abcbcd”都是X的扩展串，这里“”代表空格字符。 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。 请你写一个程序，求出字符串A、B的距离。Kp5zH4

35、6zInput有多组数据,每一组数据第一行为字符串A，第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，1K100，表示空格与其它字符的距离。Yl4HdOAAOutput每组数据一行包含一个整数，表示要求的字符串A、B的距离。Sample Inputcmcsnmn2Sample Output1021.行编辑器Problem一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符#，以表示前一个字符无效；ch4PJx4B如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符，以表示当前行中的字符均无效。如果已经在行首继续