2015合肥市第三十二届青少年信息学（计算机）竞赛小学组试题
摘要：
本试题集包含四道编程题：
植树（tree）
根据园丁人数n和小朋友人数k计算总植树数量：3n + k/3。
植树积分（points）
根据每位小朋友的植树积分排名前三及后三编号（按升序排列）。
园区最受欢迎指数（best）
在给定时间t内选择三个园区以获得最大欢迎指数之和。
最多奖励（win）
在有限能量a内通过障碍点最大化奖励值。
每道题均需严格遵循输入格式并输出指定结果范围内的数值解或特定格式化数据。
合肥市第三十二届青少年信息学（计算机）竞赛小学组试题
一、题目概况
| 题目名称 | 植树 | 植树积分 | 园区最受欢迎指数 | 最多奖励 |
|---|---|---|---|---|
| 源文件名 | tree.pas/c/cpp | points.pas/c/cpp | best.pas/c/cpp | win.pas/c/cpp |
| 输入文件名 | tree.in | points.in | best.in | win.in |
| 输出文件名 | tree.out | points. out | best. out | win. out |
| 试题类型 | 传统型 | 传统型 | 传统型 | 传统型 |
| 满分 | 100 | 100 | 100 | 100 |
| 是否有部分分 | 否 | 否 | 否 | 否 |
| 时限 | 1秒 | 1秒 | 1秒 | 1秒 |
| 内存限制 | 128M | 128M | 128M | 128M |
二、注意事项
考试时长为一小时半。
请认真审题，并严格遵守指定的输入输出格式。
建议在解决问题时先用示例数据验证思路, 然后再扩展至自定义测试用例。
每道题通常设置十组测试用例, 在规定时间内需高效完成任务, 请注意算法优化。
关于命名规则的具体内容, 请参考相关说明
(1)每题都规定了该题的英文名称。
(2)程序文件和数据文件的主文件名都是该题的英文名字。
(3)程序文件扩展名采用语言环境的默认扩展名。
(4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。
- 为确保程序正常运行，在输入数据时需从指定的数据源读取信息，并严格按照规定格式将计算结果准确无误地输出至预设的目标存储位置。
- 所有输入与输出的数据 file 均位于与主 program 处于同一层级的 directory 结构中。
- 由于 program 运行环境可能处于任意位置。
- 因此禁止在任何情况下使用驱动字母或路径相关标识符作为 file 名称。
- 请每位参赛者务必在规定的位置创建以参赛编号命名的独特子 directory。
- 并在此基础上为每一项测试任务创建独立的小型子 directory。
- 所有测试题目的 source code 则会被分别存放在各自对应的子 directory 下。
题目
1．植树（tree）
保护环境是每个人应尽的责任，在这个暑假期间也是如此。卡卡西也积极参与环保行动，在公园里与小伙伴一起植树。清晨来到公园时，满目疮痍换作绿意盎然的世界景象：不时传来园艺工人欢快的笑声声。勤快的卡卡西心中萌生出一种愿望：我也能为绿化出一份力！她急切地跑向园艺工人们，请教种植小树的办法。工人们笑着给出条件：一个园丁植3棵树、三个小朋友植1棵树，请分别用变量n表示园丁人数、k表示小朋友人数的情况下求解总植树数量的问题。小朋友们经过讨论后解答了这一需求，并顺利满足了卡卡西的愿望
输入信息仅一行，并由两个数值以空格分隔的形式给出，
这些数值分别对应于园丁人数n和小朋友人数k，
并且确保了小朋友数量恰好是3的倍数。
输出： 输出数据只有1行，为总植树数量。
样例：
输入： （tree.in）
2 9
输出： （tree.out）
9
数据范围:
0<n≤1000，0≤k≤1000
2．植树积分（points）
在卡卡西的激励下，其他伙伴也纷纷被吸引过来参与活动。大家挽起袖子、挥动铲子热切期待种植属于自己的小树以协助园艺叔叔完成任务。看着伙伴们士气高涨,卡卡西灵机一动脱口而出："亲爱的伙伴们让我们展开一场植树竞赛吧！每个人都有独特的编号参与种树都能获得相应的植树积分最终将根据每位小朋友获得的总植树积分结果，请确定前三名以及后三名的小朋友编号（注意：每位小朋友的总积分均不相同，请按照编号由低到高排序）看看谁效率最高"得到一致响应后小朋友们斗志昂扬全身心投入到种植行动中迅速完成了当天的所有树苗栽种工作每位小伙伴都收获了应得的植树积分接下来请帮助我们根据现有的数据找出前三名和后三名的小朋友编号吧
包含两行的数据。第一行为一个整数n（表示小朋友的数量），第二行为由n个用空格分隔的数字（其中第i个数字对应编号为i的小朋友）。测试数据能保证每位小朋友最终获得的总植树积分不同。
输出结果包含两行数据：第一行为累计植树积分排名前三位的小朋友编号列表；第二行为该组中的最后三名小朋友对应的编号信息。所有小朋友的编号均按升序排列。
样例：
输入： （points.in）
10
88 67 91 58 64 75 82 66 97 86
输出： （points.out）
1 3 9
4 5 8
数据范围:
0<n<100000 0<积分<100000
3．园区最受欢迎指数（best）
在卡卡西及其伙伴们的协助下, 今天整个森林公园的植树任务均已提前完成。园艺工人们看着一行行整齐排列的小树苗, 不由自主地露出了喜悦的笑容。“为了表示对你们的感谢, 我们特意准备了一张写着感谢信息的森林动物园门票作为奖品, 卡卡西, 你过来, 将这些门票分发给小朋友们吧...” 卡卡西正准备将这些门票分发给小朋友们时, 却意外地发现这些门票有些不同寻常。“叔叔, 这些门票有问题吗? 上面的内容为何缺失呢?” 卡卡西一边整理着自己的思路一边问道。“哈哈哈, 这是一张神奇的特殊性质的 tickets 啊! 你们只有能够回答出我下面的问题, 才能真正打开这扇神奇的大门哦! 并且进入园区后时间会被冻结... 在有限的时间内选择游玩3个最受欢迎的动物园区... 你们觉得可行吗？” 卡卡西胸有成竹地说道：“放心吧! 让我来安排一下好了...”
聪明的小朋友们，你们知道卡卡西是如何解决出这个问题的吗？
由三部分构成的第一部分为两个整数值t和n；第二部分为包含n项的时间序列q_i；第三部分为包含n项的人气评分s_i。
输出： 最高的受欢迎指数（游玩的3个园区受欢迎指数之和）。
样例：
输入： （best.in）
9 5
1 2 3 4 5
1 3 2 1 4
输出：(best.out)
8
数据范围:
0<t≤100 0<n≤100 0<排队时间，欢迎指数≤100
4．最多奖励（win****）****
卡卡西果然令人大跌眼镜，在极短时间内就完美解决了"园区最受欢迎指数"这一难题！当空出现一道耀眼的光芒时，在场的小朋友们顿时惊讶得连眼皮都跳了起来——原来所有小朋友手上的动物园门票都变得清晰起来，并且升至空中后开始慢慢聚集在一起！这时他们才意识到自己竟然能看到如此壮观的画面——这些手里的门票竟然能够自行组合成一座彩虹-colored的大桥！孩子们兴奋得努力揉着眼睛难以置信地盯着这座神奇的"空中桥梁"——哦不！这难道是天方夜谭？随后卡卡西带着孩子们见到了园内的各个叔叔阿姨，并有条不紊地带领他们走向这座跨越天空的巨大彩虹桥！
不一会儿功夫,动物园就到了,卡卡西和小伙伴们沿着桥梁缓缓下行。令人心生疑惑的是,这样一个原本应该是充满活力的动物园此刻却安静得令人难以置信,完全没有组织任何活动,大门紧闭着不动声色。小朋友们内心有些忐忑不安,细心观察后发现,卡卡西正站在大门外张望,他手里的告示上贴着一道数学题:原来园长被困在迷宫中由一位神秘的绿巨人把守,只有解开这道题才能获救！这道题的意思是说:假定从城堡A出发到城堡B需要跨越若干障碍物每个障碍物都需要消耗一定的能量但也可能带来一定的奖励人们可以通过传送门到达任意障碍物的位置那么在有限的能量预算内如何选择障碍点才能使抵达城堡B时获得最多的奖励呢？
卡卡西咬紧牙关，充满信心地宣布道："亲爱的小伙伴们，请相信我们一定能够解开这个难题，并且成功营救我们的园长！"一群充满智慧的小朋友，请你们共同努力来完成这次挑战吧！
输入数据由三行组成。第一行为两个整数a和n（其中a表示出发时的能量），第二行为n个整数（每个整数表示清除第i个障碍所需的能量），第三行为n个整数（每个整数表示清除第i个障碍获得的奖励）。
输出： 最多的奖励。
样例：
输入： （win.in）
10 5
2 3 4 2 5
1 7 4 3 4
输出：(win.out)
14
数据范围:
0<a<=1000 0<n<=100 0<障碍所需能量，奖励<100