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

黄淮学院第六届程序设计竞赛试题黄淮学院第六届程序设计竞赛试题 考试时间三个小时 共七道试题考试时间三个小时 共七道试题 试题一试题一 素数问题素数问题 走进世博园某信息通信馆 参观者将获得前所未有的尖端互动体验 一场 充满创想和喜悦的信息通信互动体验秀将以全新形式呈现 从观众踏入展馆的 第一步起 就将与手持终端密不可分 人类未来梦想的惊喜从参观者的掌上展 开 在等候区的梦想花园中 参观者便开始了他们奇妙的体验之旅 等待中的游客 可利用手机等终端参加互动小游戏 与梦想剧场内的虚拟人物 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 行 每行只有一个整数对 中间用空格分开 表示一个点的 坐标 没有一个点会出现两次 标准输出标准输出 输出一行 表示一条直线能覆盖的最多的点数 输入样例输入样例 5 1 1 3 3 9 10 10 10 10 11 输出样例输出样例 3 试题三试题三 穿越沙漠问题穿越沙漠问题 在二战中 往前方运输物质的车队要穿过广阔的沙漠地带 但是在穿越的 过程中每辆卡车都要消耗掉很多的汽油 为了保证卡车能穿过沙漠必须在沙漠 中建立一些加油点用来储存汽油 现在有一辆重型卡车欲穿过 1000 公里的沙漠 卡车耗油为 1 公升 公里 卡车总载油能力为 500 公升 显然卡车装一次油是过 不了沙漠的 因此司机必须设法在沿途建立几个储油点 使卡车能顺利穿越沙 漠 试问司机如何建立这些储油点 每一储油点应存多少汽油 才能使卡车以 消耗最少汽油的代价通过沙漠 标准输入标准输入 本试题没有输入 标准输出标准输出 输出每个储油点的编号 该储油点离出发点的距离和该储油点的储油量 输出样例输出样例 储油点编号 离出发点的距离 储油量 1 XXX XXX 2 XXX XXX 3 XXX 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 试题六试题六 Hang over How 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 Input The 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 Output For 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 Input 1 00 3 71 0 00 Sample Output 3 61 试题七试题七 Crashing Balloon On 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 his her score the product of the numbers on the balloons he she 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 his her opponent s score The player with the lower score is presumed to have told the truth because if he she were to lie about his her score he she 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 o