2008年亳州市青少年信息学竞赛试题.doc

2008年“安联杯”全省青少年信息学奥林匹克竞赛（阜阳赛区选拔赛）试题2008年“安联杯”全省青少年信息学奥林匹克竞赛（阜阳赛区选拔赛）试题竞赛时间：2008年3月30日上午9：0012：00题目一览题目名称歌手统分切饼问题数字的乘积根铺路问题程序文件scorecakenumberroad输入文件score.incake.innumber.inroad.in输出文件score.outcake.outnumber.outroad.out时限1秒1秒1秒1秒注意事项：1 务必看清题目，严格按照所要求的格式输入、输出。2 在调试程序时请先用题目中的示例数据，然后再自行设计多组测试数据进行调试。3 测试有严格的时间限制，请尽可能优化算法。4 命名规则：（1） 每题都规定了该题的英文名称。（2） 程序文件和数据文件的主文件都是该题的英文名字。（3） 程序文件扩展名采用语言环境的默认扩展名。（4） 数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。5 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中，行首不得有空格，输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在的目录是不确定的，因此不允许在程序中含有盘符信息和任何形式的路径信息。6 选手在竞赛结束时应在硬盘指定位置建立以参赛号命名的文件夹，并将所完成各题的源程序文件和编译所产生的可执行文件（即扩展名为.exe的文件）拷贝到该文件夹中。1.歌手统分（score.pas/c/cpp）【问题描述】最近，我市举行了一届“青年歌手大奖赛”，邀请N名裁判给某歌手打分。评分原则是去掉一个最高分，去掉一个最低分，剩下的分数的平均值即为该歌手的最终得分m。裁判给分的范围是60分数100。现请你编写程序给该歌手统分，统计出该歌手的最终得分m（小数点后保留两位小数）。【输入】输入文件score.in包含N+1行；第1行是一个正整数N，表示裁判员的个数；第2N+1行，每行一个数分别为每个裁判员给该歌手打的分数。【输出】输出文件score.out仅包含一行为一个数m，表示该歌手的最终得分【输入输出样例】score.inscore.out596.5685.5597.8898.6590.8895.11【限制】40%的数据满足：3N1080%的数据满足：3N100100%的数据满足：3N10002.切饼问题（cake.pas/c/cpp）【问题描述】王小二自夸刀工不错，有人放一张大的煎饼在砧板上，问他：“饼不许离开砧板，切n刀最多能切多少块？”王小二请你编写程序求出最多块理论值m.【输入】输入文件cake.in仅包含1行为一个整数n，表示切的刀数。【输出】输出文件cake.out仅包含1行为一个整数m，表示切出的最多块数。【输入输出样例】cake.incake.out12【限制】40%的数据满足：0n10080%的数据满足：0n50000100%的数据满足：0n10000003. 数字的乘积根（number.pas/c/cpp）【问题描述】求数字n的乘积根：定义：正整数n中非零数字的乘积称为该数的数字乘积。如1620的数字乘积为162=12，12的数字乘积为12=2。定义：正整数n的数字乘积根为反复取该整数的数字乘积，直到最后的数字乘积为一位数字，这个一位数字就叫该正整数的数字乘积根m。例如：1620的数字乘积为162=12，12的数字乘积为12=2，因此1620的数字乘积根m为2 。【输入】输入文件number.in仅包含1行为一个正整数n。【输出】输出文件number.out仅包含1行为一个一位整数m,表示数字n的乘积根。【输入输出样例】number.innumber.out16202【限制】50%的数据满足：1n10000100%的数据满足：1n100000004. 铺路问题【问题描述】我市正在筹划“村村通工程”，就是在我市村与村之间铺设水泥公路网，使村与村之间互相连通，方便人们生活。每两个村庄之间都可以铺设一条公路，相应地都要付出一定代价w万元，对于n个村庄之间最多可能铺设n(n-1)/2条公路，而实际上，对于n个村庄只需要n-1条公路就可以相互连通了。现在，市建设委员会已对每两个村庄之间进行了实地勘察，考虑到实际情况，具有可行性的共有e（en-1）条，并预估出各条公路要付出的代价wi(i=1、2e)万元，为了尽量节约资金并使村与村之间都可达，现请你编写程序设计出铺路的一个最佳方案，使村与村之间都可达且总的耗费c最少？例如：V1V3V210万元20万元V1V3V210万元20万元30万元如图：V1、V2、V3分别代表三个村庄，其中10万元、20万元、30万元分别为公路V1V2、V2V3、V3V1的造价。最佳方案为铺设两条公路：V1V2造价10万元和V2V3造价20万元，总共耗费30万元最少。【输入】输入文件 road.in的第1行为两个正整数，用一个空格隔开：n e其中n表示村庄数，e表示可能铺设的公路条数从2e+1行，每行为三个正整数，它们之间用一个空格隔开：i j wij其中i、j为两个村庄的序号，表明这两个村庄之间可建一条公路，wij为该条公路的造价（1in,1jn, wi100000万元）【输出】输出文件road.out为包含n行从1n-1行为三个正整数，它们之间用一个空格隔开：i j wij其中i、j为两个村庄的序号，表明这两个村庄之间要建一条公路，wij为该条公路的造价第n行为一个正整数c其中c