2011年湘南学院ACM程序设计大赛

《2011年湘南学院ACM程序设计大赛》由会员分享，可在线阅读，更多相关《2011年湘南学院ACM程序设计大赛（9页珍藏版）》请在装配图网上搜索。

1、2011年湘南学院ACM程序设计大赛1、免费馅饼Problem Description都说天上不会掉馅饼，但有一天 gameboy 正走在回家的小径上，忽然天上 掉下大把大把的馅饼。说来 gameboy 的人品实在是太好了，这馅饼别处都不掉， 就掉落在他身旁的 10米范围内。馅饼如果掉在了地上当然就不能吃了，所以 gameboy 马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在 小径上接。由于 gameboy 平时老呆在房间里玩游戏，虽然在游戏中是个身手敏 捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围 内接住坠落的馅饼。现在给这条小径如图标上坐标：为了使

2、问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这 11 个 位置。开始时 gameboy 站在 5 这个位置，因此在第一秒，他只能接到 4,5,6 这三 个位置中期中一个位置上的馅饼。问 gameboy 最多可能接到多少个馅饼？(假 设他的背包可以容纳无穷多个馅饼)Input输入数据有多组。每组数据的第一行为以正整数n(OvnvlOOOOO),表示有n 个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0vTv100000), 表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。 n=0 时输入结束。Output每一组输入数据对应一行输出。输出一个整数m

3、,表示gameboy最多可能 接到 m 个馅饼。Sample Input65 14 16 17 27 28 3 0Sample Output42、畅通工程Problem Description 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直 接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交 通(但不一定有直接的道路相连，只要互相间接通过道路可达即可)。问最少还 需要建设多少条道路？Input 测试输入包含若干测试用例。每个测试用例的第 1 行给出两个正整数，分别 是城镇数目N (v 1000 )和道路数目M;随后的M行对应M条道路，每行给出 一对正整

4、数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从 1到N编号。注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。Output对每个测试用例，在1行里输出最少还需要建设的道路数目。Sample Input4 21 34 33 31 21 32 35 21 23 5999 00Sample Output1029983、奥运排序问题Problem Description 按要求，给国家进行排名。Input 有多组数据。第一行给出国家数N,要求排名的国家数M,国家号从0到N-1。第二行开始的 N 行给定国家或

5、地区的奥运金牌数，奖牌数，人口数（百万）。 接下来一行给出 M 个国家号。Output 排序有4 种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例 对每个国家给出最佳排名排名方式 和 最终排名格式为: 排名 :排名方式 如果有相同的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌 总数 奖牌总数 金牌人口比例 奖牌人口比例 如果有并列排名的情况，即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4. 每组数据后加一个空行。Sample Input4 44 8 16 6 24 8 22 12 40 1 2 34 28 10 18 11 28 12 38 13

6、40 3Sample Output1:31:12:11:21:11:14、ZOJProblem Description读入一个字符串，字符串中包含ZOJ三个字符，个数不一定相等，按ZOJ 的顺序输出，当某个字符用完时，剩下的仍然按照ZOJ的顺序输出。Input题目包含多组用例，每组用例占一行，包含ZOJ三个字符，当输入“E时表示 输入结束。1=length=100。Output对于每组输入，请输出一行，表示按照要求处理后的字符串。 具体可见样例。Sample InputZZOOOJJJZZZZOOOOOJJJZOOOJJESample OutputZOJZOJOJZOJZOJZOJZOOZOJ

7、OJO5、考新郎国庆期间,省城 HY 刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富 一些,司仪临时想出了有一个有意思的节目,叫做考新郎,具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板.看来做新郎也不是容易的事情.假设一共有N对新婚夫妇,其中有M个新郎找错了新娘，求发生这种情况一共有 多少种可能.Input输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据， 每行包含两个整数N和M(lvMv=Nv=20)。Output

8、 对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的 输出占一行。Sample Input22 23 2Sample Outputl36、糖果大战Problem Description生日Party结束的那天晩上，剩下了一些糖果，Gandon想把所有的都统统拿 走， Speakless 于是说：“可以是可以，不过我们来玩 24 点，你不是已经拿到了 一些糖果了吗？这样，如果谁赢一局，就拿走对方一颗糖，直到拿完对方所有的 糖为止。”如果谁能算出来而对方算不出来，谁就赢，但是如果双方都能算出或 者都不能，就算平局，不会有任何糖果的得失。Speakless 是个喜欢提前想问题的人，既

9、然他发起了这场糖果大战，就自然很想 赢啦(不然可就要精光了 -_-)。现在他需要你的帮忙，给你他每局赢的概率和 Gardon 每局赢的概率，请你给出他可能获得这场大战胜利的概率。Input每行有四个数，Speakless手上的糖果数N、Gardon手上的糖果数 M(0v=N,Mv=50)、一局Speakless能解答出来的概率p、一个问题Gardon能解答 出来的概率 q(0=p,q=1)。Output每行一个数，表示 Speakless 能赢的概率(用百分比计算，保留到小数点后 2 位)。Sample Input50 50 0.5 0.510 10 0.51 0.550 50 0.51 0.

10、5Sample Output0.500.600.887、RP 问题Problem Description 在人类社会中，任何个体都具有人品，人品有各种不同的形式，可以从一种 形式转换为另一种形式，从一个个体传递给另一个个体，在转换和传递的过程中， 人品不会消失，也不被能创造，这就是，人品守恒定律！ 人品守恒定律更形象的描述，当发生一件好事，你从中获利，必定消耗一定量 RP;当发生一件不幸的事，你在其中有所损失，必定积攒一定量RP。假设在一个时间段内在你身上可能会发生N个事件，每个事件都对应一个RP变 化值a、RP门槛值b和获益值c。当RP变化值a为正，获益值c必定为负，只 有你当前的RP值小于

11、等于RP门槛值b的时候，此事件才有可能发生，当此事 件发生时，你的RP值将增加lai，获益值将减少Icl。反之，当RP变化值a为负， 获益值c必定为正，只有你当前的RP值大于等于RP门槛值b的时候，此事件 才有可能发生，当此事件发生时，你的RP值将减少lai，获益值将增加lei。 一个事件在满足上述RP条件的前提下，未必会发生。假设在这段时间之前你所 具有的RP值和获益值都为0那么过了这段时间后，你可能达到的最大获益值 是多少？ 注意：一个人的所具有的RP值可能为负。Input输入数据的第一行为一个正整数T，表示有T组测试数据。每组测试数据的 第一行为一个正整数N (0 N = 1000)，表

12、示这个时间段在你身上可能发生N个 事件。接下来N行，每行有三个整数a, b, c (0 = lai = 10, 0 = ibl = 10000, 0 = icl 2，就是说至除了出发点以外至少要经过2个其 他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这 样的路线，并且花费越少越好。Input第一行是2个整数N和M(N = 100, M = 1000)，代表景区的个数和道路 的条数。接下来的M行里，每行包括3个整数a,b,c.代表a和b之间有一条通路，并且需 要花费c元(c = 100)。Output对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如 果

13、找不到的话，输出 Its impossible.Sample Input3 31 2 12 3 11 3 13 31 2 11 2 32 3 1Sample Output3Its impossible.9、Repair the WallProblem DescriptionLong time ago , Kitty lived in a small village. The air was fresh and the scenery was very beautiful. The only thing that troubled her is the typhoon.When the typh

14、oon came, everything is terrible. It kept blowing and raining for a long time. And what made the situation worse was that all of Kittys walls were made of wood.One day, Kitty found that there was a crack in the wall. The shape of the crack isa rectangle with the size of lxL (in inch). Luckly Kitty g

15、ot N blocks and a saw(锯子) from her neighbors.The shape of the blocks were rectangle too, and the width of all blocks were l inch. So, with the help of saw, Kitty could cut down some of the blocks(of course she could use it directly without cutting) and put them in the crack, and the wall may be repa

16、ired perfectly, without any gap.Now, Kitty knew the size of each blocks, and wanted to use as fewer as possible of the blocks to repair the wall, could you help her ?InputThe problem contains many test cases, please process to the end of file( EOF ). Each test case contains two lines.In the first li

17、ne, there are two integers L(0Ll000000000) and N(0=N600) which mentioned above.In the second line, there are N positive integers. The ith integer Ai(0vAiv1000000000 ) means that the ith block has the size of lxAi (in inch).OutputFor each test case , print an integer which represents the minimal number of blocks are needed.If Kitty could not repair the wall, just print impossible instead.Sample Input5 33 2 15 22 1Sample Output2impossible