黄淮学院C程序设计第六届竞赛试题.docx

黄淮学院第六届程序设计竞赛试题考试时间三个小时，共七道试题试题一 素数问题走进世博园某信息通信馆，参观者将获得前所未有的尖端互动体验，一场充溢创想和喜悦的信息通信互动体验秀将以全新形式呈现，从观众踏入展馆的第一步起，就将及手持终端密不行分，人类将来幻想的惊喜从参观者的掌上绽开。在等候区的幻想花园中，参观者便开场了他们奇异的体验之旅，等待中的游客可利用手机等终端参与互动小嬉戏，及幻想剧场内的虚拟人物Kr Kong进展猜数竞赛。当屏幕出现一个整数x时，若你能比Kr Kong更快的发出最接近它的素数答案，你将会获得一个意想不到的礼物。例如：当屏幕出现22时，你的回容许当是23；当屏幕出现8时，你的回容许是7；若x本身是素数，则答复x；若接近x的素数有两个时，则答复大于它的素数。标准输入 第一行：N 要竞猜的整数个数 接下来有N行，每行只有一个正整数 x标准输出 输出有N行，每行是对应x的最接近它的素数。约束条件 1<=N<=5 1<=x<=1000样例输入3 8 23 25样例输出7 23 23试题二救灾投放物质问题灾区已经特别困难，灾民须要帐篷、衣物、食品和血浆。可通往灾区的道路到处都是塌方，70%以上的路面损坏，桥梁全部被毁。中国空军马上启动应急预案，绽开史上最大强度非作战空运行动，打算向灾区空投急需物资。由于余震不断，天气恶劣，怎样保证在一次飞行中将空投的物资投放到尽可能多的居民点是一个特别重要的问题。经过空中观测，许多居民点大都在一条线路上。你能否给出一个线路使一次飞行投放的物质到达最大化？标准输入 第一行：N 要输入的整数对的个数(1<N<700) 接下来有N行，每行只有一个整数对（中间用空格分开），表示一个点的坐标，没有一个点会出现两次。标准输出 输出一行，表示一条直线能覆盖的最多的点数。输入样例51 13 39 1010 1010 11输出样例3试题三 穿越沙漠问题在二战中，往前方运输物质的车队要穿过广袤的沙漠地带，但是在穿越的过程中每辆卡车都要消耗掉许多的汽油，为了保证卡车能穿过沙漠必需在沙漠中建立一些加油点用来储存汽油。如今有一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1公升/公里，卡车总载油实力为500公升，明显卡车装一次油是过不了沙漠的。因此司机必需设法在沿途建立几个储油点，使卡车能顺当穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？标准输入 本试题没有输入。 标准输出 输出每个储油点的编号、该储油点离动身点的间隔 和该储油点的储油量。输出样例储油点编号 离动身点的间隔 储油量1XXX XXX2XXX XXX3XXX XXX（其中XXX代表详细的间隔 或储油量）试题四旅行者费用问题一个美国旅行代理商常常被要求去估计开车从一个城市旅行至另一城市的最小费用。他有一个在通常路途上的大多数加油站的列表。列表包括了全部加油站的位置及当前每加仑汽油的价格。为了简化估计费用的过程，代理商运用了一下的简化汽车驾驶员行为的规则：（1）除非汽车无法用邮箱里的汽油到达下一个加油站（假如有的话）或目的地，在邮箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来。（2）在每一个停下的加油站驾驶员总是将油箱加满。（3）在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上花去2.00元。（4）在驶向加油站或目的地时，驾驶员不须要超过必需量的汽油。不须要“平安余量”。（5）驾驶员开场旅行时油箱总是满的。（6）在每个加油站付款时四舍五入到分（1元=100分）。你必需写一个程序以估计驾驶员在旅程上只是要为汽油和食品付多少钱。输入 程序的输入将由若干个对应不同的旅程的数据项组成，每个数据项由若干信息行组成。开场的2行给出了动身地和目的地的信息，数据项的后继行代表了路途上的加油站，每个加油站用一行表示。下面是输入数据中数据项的准确格式及其含义。第一行：一个实数表示从动身地到目的地的间隔 （单位：公里）；第二行：三个实数及一个整数，中间用空格分开。 （1）第一个实数是汽车油箱的最大的容量（加仑）； （2）第二个数据是汽车每加仑汽油可以行使的英里数； （3）第三个实数是汽车在动身地城市加满油箱的费用（单位：元）； （4）整数（小于51）是路途上加油站的数据。接下来的每一行：两个实数，中间用空格分开： （1）第一个实数是从动身地到加油站的间隔 （单位：公里）； （2）第二个实数是该加油站出售的汽油每加仑的价格（单位：分）；数据项中的全部数据都是正的，一条路途上的加油站依据其到动身地的间隔 递增排列。路途上不存在这样的加油站，它到动身点的间隔 大于从动身点到目的地的间隔 。每条路途上的加油站都被适当地支配以使得任何汽车都可以从动身地开到目的地。输入数据中若某行为一个负数则表示输入数据完毕。输出 对于输入中的每个数据项，你的程序必需打印数据项编号以及一个给出了准确到分的汽油和食品的最小总费用。总费用必需包括开场时在动身地加满油箱的费用。下面是一个样例输入以及相应的正确的输出。样例输入 475.6 11.9 27.4 14.98 6 102.0 99.9 220.0 132.9 256.3 147.9 275.0 102.9 277.6 112.9 381.8 100.9 -1样例输出27.31试题五 合并果子    在一个果园里，多多已经将全部的果子打了下来，而且按果子的不同种类分成了不同的堆。多多确定把全部的果子合成一堆。     每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，全部的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。     因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节约体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多消耗的体力最少，并输出这个最小的体力消耗值。     例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，消耗体力为3。接着，将新堆及原先的第三堆合并，又得到新的堆，数目为12，消耗体力为12。所以多多总共消耗体力=3+12=15。可以证明15为最小的体力消耗值。 【输入】     输入包括两行，第一行是一个整数n(1<n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<ai<=20000)是第i种果子的数目。 【输出】     输出包括一行，这一行只包含一个整数，也就是最小的体力消耗值。输入数据保证这个值小于231。 【样例输入】3 1 2 9 【样例输出】15 试题六HangoverHow far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We're assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + . + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). InputThe input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.OutputFor each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.Sample Input1.003.710.00Sample Output3 61 试题七Crashing BalloonOn every June 1st, the Children's Day, there will be a game named "crashing balloon" on TV.  The rule is very simple.  On the ground there are 100 labeled balloons, with the numbers 1 to 100.  After the referee shouts "Let's go!" the two players, who each starts with a score of  "1", race to crash the balloons by their feet and, at the same time, multiply their scores by the numbers written on the balloons they crash.  After a minute, the little audiences are allowed to take the remaining balloons away, and each contestant reports hisher score, the product of the numbers on the balloons heshe's crashed.  The unofficial winner is the player who announced the highest score. Inevitably, though, disputes arise, and so the official winner is not determined until the disputes are resolved.  The player who claims the lower score is entitled to challenge hisher opponent's score.  The player with the lower score is presumed to have told the truth, because if heshe were to lie about hisher score, heshe would surely come up with a bigger better lie.  The challenge is upheld if the player with the higher score has a score that cannot be achieved with balloons not crashed by the challenging player.  So, if the challenge is successful, the player claiming the lower score wins. So, for example, if one player claims 343 points and the other claims 49, then clearly the first player is lying; the only way to score 343 is by crashing balloons labeled 7 and 49, and the only way to score 49 is by crashing a balloon labeled 49.  Since each of two scores requires crashing the balloon labeled 49, the one claiming 343 points is presumed to be lying. On the other hand, if one player claims 162 points and the other claims 81, it is possible for both to be telling the truth (e.g. one crashes balloons 2, 3 and 27, while the other crashes balloon 81), so the challenge would not be upheld. By the way, if the challenger made a mistake on calculating his/her score, then the challenge would not be upheld. For example, if one player claims 10001 points and the other claims 10003, then clearly none of them are telling the truth. In this case, the challenge would not be upheld. Unfortunately, anyone who is willing to referee a game of crashing balloon is likely to get over-excited in the hot atmosphere that heshe could not reasonably be expected to perform the intricate calculations that refereeing requires.  Hence the need for you, sober programmer, to provide a software solution. InputThe input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Pairs of unequal, positive numbers, with each pair on a single line, that are claimed scores from a game of crashing balloon. OutputFor each test case,Numbers, one to a line, that are the winning scores, assuming that the player with the lower score always challenges the outcome. Sample Input343 4962 360.00Sample Output4962