(完整版)nb2007年4月初中组复赛

1、宁波市第 22 届中小学生计算机程序设计竞赛决赛试题(初中组 )考生须知：1 、考试时间为 150 分钟，满分 400 分。2 、考生不得携带任何存储设备。3 、考试开始前，请先确定 D 盘内容不会被还原，如有问题请监考老师解决。4 、上机考试时要随时注意保存程序。5、每题都必须提交源程序和编译后的可执行程序( 程序的命名办法见每题中的规定 ) ，且必须存放到指定的文件夹内 ( 放错位置的视为无效 ) 。测试时，以源程序为准。题号题目名称提交的源程序提交的可执行程序每个测试允许测试点每个测试点时限内存数目点分值1分解数字factor pas ccppfactor exe2秒64MB10102最

2、大约数和maxsumpas ccppmaXSUm eXe1秒64MB10103单词背诵letter pas ccppIetter exe1秒64MB10104关路灯powe r pas ccpppowerexe1秒64MB1010试题一：分解数字(100 分 )(源程序名： factorpas 或 factor c 或 factor cpp ，编泽后可执行程序名： factor exe)【问题描述】输入自然数 n 和 m，输出 n 的所有分解和式，分解后的每一项都不大于 m。组成和式的数字自左至右构成一个不降的序列，不能重复。如以下三个分解式 4=1+1+2； 4=1+2+1； 4=2+l+1

3、 中只有第一个符合要求。各组方案之间按照字典顺序输出。【输入】 输入文件 factor in 中有两行， 每行只有一个正整数。第一行是 n，第二行是 m。【输出】输出文件 factor out 含若干行，每行先输出标号，注意标号后有： ，然后输出一个和式。【数据限制】本题共有 10 组测试数据，每组 10 分，共 100 分。100的数据 1n50，1m n【样例输入】【样例输出】71：7=1+1+1+1+1+1+142：7=1+l+1+1+1_23：7=1+1+1+1+34：7=1+1+1+2+25：7=l+1+1+46：7=1+1+2+37：7=1+2+2+28：7=1+2+49：7=1+

4、3+310：7=2+2+311：7=3+4试题二：最大约数和(100 分 )(源程序名： maxsum，扩展名 pas 或C 或 cpp ，编译后可执行程序名：maxsumexe)【问题描述】选取和不超过S 的若干个不同的正整数， 使得所有数的约数 ( 不含它本身 ) 之和最大。如：输入一个数 11，则可取数字 4 和 6，可以得到约数和的最大值 (1+2)+(1+2+3)=9【输入】输入文件maxsum in 中只有一个正整数 S。【输出】输出文件maxsum out 只有一行，该行只有一个整数，为求得的最大值。【数据限制】【样例输入】【样例输出】本题共有 10 组测试数据，每组 10 分，

5、共 100 分。91 130 的数据， 1s10，100的数据， 1s1000试题三：单词背诵(100 分 )( 源程序名：letterpas 或 letterC 或 lettercpp，编译后可执行程序名： letterexe)【问题描述】乐乐在背单词，他发现当背诵了单词beauty以后，再接着背诵单词beautiful就会觉得容易许多。 由于有很多单词要背，他希望找到一种好的背诵顺序。单词 A 和它的前一个单词 B 的最大公共前缀的长度称为背诵单词 A的 便 利 值 ( 例 如 ： B=beauty ，A=beautiful ，则 A 的便利值是 len(A，B)=len( beant )

6、=5),我们认为一个背诵单词 A 的花费是它的长度( 例如： beautiful的长度 len( beautiful )=9) 与它的便利值之差 ( 对于上述例子背诵A 的花费为 9-5=4) 。请你求一个背诵顺序，使得背诵这些单的花费总和最小。假设一开始你什么单词都不记得。【输入】输入文件 letter in 中有若干行。第一行只有样例输入样例输出一个整数 N，表示单词总数。接下来N 行，每行一个单词。522【输出】输出文件 letter out 只有一行，beauty该行只有一个整数，表示求得的最小花费总和。beanutiful【数据限制】本题共有10 组测试数据，flower每组 10

7、分，共 100 分。man30 的数据， 1n100dog100 的数据， 1n10000100的数据，每个单词的长度在1 至 20 之间试题四：关路灯 (100 分 )(源程序名：power-pas 或 powerC或 powercpp，编译后可执行程序名： powerexe)【问题描述】某一村庄在一条路线上安装了 n 盏路灯，每盏灯的功率 ( 单位时间的耗电量 ) 有大有小。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关， 但是老张不知道怎样去关灯才能够最节省电。 他每

8、天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为，先算一下左边路灯的总功率， 再算一下右边路灯的总功率， 然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，这样可以最省电。而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。现在已知老张走的速度为 1 米秒；每个路灯的位置 ( 是一个整数，即照路线起点的距离，单位：米 ) ；以及功率（ W），老张关灯所用的时间很短而可以忽略不计） 。请你为老张编一程序来安排关灯的顺序， 使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了） 。【输入】输入文件power.in 中有若干行。第1 行是两个数字n 和 c, 分别表示路灯数和老张所处位置的路灯号；第 2 行至第 n+1 行，每行有两个整数。 其中第 k+1 行的第一个整数表示第 K 盏灯离路线起点的距离， 第二个整数表示第k 盏灯的功率。 以上 n+1 行中，每行的两个整数之间都有一个空格分隔。样例输入样例输出【输出】53270210此时关灯顺序为输出文件 power.out只有一行，该行只有一个整32034215，不必输出这个数，表示求得的最少耗电量。 （单位： j,1j=1w.秒）20关灯顺序 56308 10【数据限制】 本题