《全国信息学奥林匹克联赛(noip2007)复赛》由会员分享，可在线阅读，更多相关《全国信息学奥林匹克联赛(noip2007)复赛（6页珍藏版）》请在金锄头文库上搜索。
1、全国信息学奥林匹克联赛（NOIP2007）复赛 普及组第 1 页 共 6 页全国信息学奥林匹克联赛（全国信息学奥林匹克联赛（NOIP2007NOIP2007）复赛）复赛普及组题目一览题目一览题目名称题目名称 奖学金奖学金纪念品分组纪念品分组守望者的逃离守望者的逃离Hanoi 双塔问题双塔问题代号scholargroupescapehanoi输入文件scholar.ingroup.inescape.inhanoi.in输出文件scholar.outgroup.outescape.outhanoi.out时限1 秒1 秒1 秒1 秒(2007 年年 11 月月 17 日日 3 小时完成小时完成)说
2、明： 1. 文件名（程序名和输入输出文件名）必须使用小写 2. C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3. 全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存 256M。全国信息学奥林匹克联赛（NOIP2007）复赛 普及组第 2 页 共 6 页1奖学金奖学金(scholar.pas/c/cpp)【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末，每个学生都有 3 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分
3、和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5 名学生的学号和总分。注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 2795 279这两行数据的含义是：总分最高的两个同学的学号依次是 7 号、5 号。这两名同学的总分都是 279（总分等于输入的语文、数学、英语三科成绩之和） ，但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是：5 2797 27
4、9则按输出错误处理，不能得分。【输入】输入文件 scholar.in 包含 n+1 行：第 1 行为一个正整数 n，表示该校参加评选的学生人数。第 2 到 n+1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100 之间。第 j 行的 3 个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1n（恰好是输入数据的行号减 1） 。所给的数据都是正确的，不必检验。【输出】输出文件 scholar.out 共有 5 行，每行是两个用空格隔开的正整数, 依次表示前 5 名学生的学号和总分。全国信息学奥林匹克联赛（NOIP2007）复赛 普及组第
5、3 页 共 6 页【输入输出样例 1】scholar.inscholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 986 265 4 264 3 258 2 244 1 237【输入输出样例 2】scholar.inscholar.out 8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 988 265 2 264 6 264 1 258 5 258【限制】50%的数据满足：各学生的总成绩各不相同100%的数据满足：6=n=300
6、全国信息学奥林匹克联赛（NOIP2007）复赛 普及组第 4 页 共 6 页2纪念品分组纪念品分组(group.pas/c/cpp)【题目描述】 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获 得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪 念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所 有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。【输入】输入文件 group.in 包含 n+2 行：第 1 行包括一个整数 w，为每
7、组纪念品价格之和的上限。第 2 行为一个整数 n，表示购来的纪念品的总件数。第 3n+2 行每行包含一个正整数 pi (5 = pi = w)，表示所对应纪念品的价格。【输出】输出文件 group.out 仅一行，包含一个整数，即最少的分组数目。【输入输出样例】 group.ingroup.out100 9 90 20 20 30 50 60 70 80 906【限制】50%的数据满足：1 = n = 15100%的数据满足：1 = n = 30000, 80 = w = 200全国信息学奥林匹克联赛（NOIP2007）复赛 普及组第 5 页 共 6 页3守望者的逃离守望者的逃离(escape
8、.pas/c/cpp)【问题描述】恶魔猎手尤迪安尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。守望者在 与尤迪安尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。为了杀死守望者，尤迪安尤迪安开始对这个 荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。守望者的跑步速度为 17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 1s 内移动 60m， 不过每次使用闪烁法术都会消耗魔法值 10 点。守望者的魔法值恢复的速度为 4 点/s，只有处在原 地休息状态时才能恢复。 现在已知守望者的魔法初值 M，他所在的初始位置与岛的出口之间的距离 S，岛
9、沉没的时间 T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守 望者在剩下的时间内能走的最远距离。注意：守望者跑步、闪烁或休息活动均以秒(s)为单位，且 每次活动的持续时间为整数秒。距离的单位为米(m)。【输入】输入文件 escape.in 仅一行，包括空格隔开的三个非负整数 M, S, T。 【输出】输出文件 escape.out 包含两行：第 1 行为字符串“Yes”或“No” （区分大小写） ，即守望者是否能逃离荒岛。第 2 行包含一个整数。第一行为“Yes” （区分大小写）时表示守望者逃离荒岛的最短时间； 第一行为“No” （区分大小写）时表示守望者
10、能走的最远距离。【输入输出样例 1】 escape.inescape.out39 200 4No 197【输入输出样例 2】 escape.inescape.out36 255 10Yes 6【限制】 30%的数据满足：1 = T = 10, 1 = S = 10050%的数据满足：1 = T = 1000, 1 = S = 10000100%的数据满足：1 = T = 300000, 0 = M = 1000, 1 = S = 108.全国信息学奥林匹克联赛（NOIP2007）复赛 普及组第 6 页 共 6 页4Hanoi 双塔问题双塔问题(hanoi.pas/c/cpp)【问题描述】给定
11、A、B、C 三根足够长的细柱，在 A 柱上放有 2n 个中间有孔的圆盘，共有 n 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为 n=3 的情形） 。现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。要求：（1）每次只能移动一个圆盘；（2）A、B、C 三根细柱上的圆盘都要保持上小下大的顺序；任务：设 An为 2n 个圆盘完成上述任务所需的最少移动次数，对于输入的 n，输出 An。【输入】输入文件 hanoi.in 为一个正整数 n，表示在 A 柱上放有 2n 个圆盘。【输出】输出文件 hanoi.out 仅一行，包含一个正整数, 为完成上述任务所需的最少移动次数 An。【输入输出样例 1】hanoi.inhanoi.out12【输入输出样例 2】hanoi.inhanoi.out26【限制】对于 50%的数据，1=n=25对于 100%的数据，1=n=200【提示】设法建立 An与 An-1的递推关系式。
