宁波市第22届中小学生计算机程序设计竞赛决赛试题（初中组）2007年4月
宁波市第22届中小学生计算机程序设计竞赛决赛试题
（初中组）
考生须知：
1、考试时间为150分钟，满分400分。 2、考生不得携带任何存储设备。
3、考试开始前，请先确定D盘内容不会被还原，如有问题请监考老师解决。 4、上机考试时要随时注意保存程序。 5、每题都必须提交源程序和编译后的可执行程序（程序的命名办法见每题中的规定）， 且必须存放到指定的文件夹内（放错位置的视为无效）。测试时，以源程序为准。 6、考试结束后，不得关机，否则后果自负。 题号 1 2 3 4 题目名称 分解数字 提交的源程序 factor.pas/c/cpp 提交的 可执行程序 factor.exe 每个测试点时限 2秒 1秒 1秒 1秒 允许 内存 64MB 64MB 64MB 64MB 测试点每个测试数目 点分值 10 10 10 10 10 10 10 10 最大约数和 maxsum.pas/c/cpp maxsum.exe 单词背诵 letter.pas/c/cpp letter.exe 关路灯 power.pas/c/cpp power. exe 试题一：分解数字（100分）
（源程序名：factor.pas或factor.c或factor.cpp，编译后可执行程序名：factor.exe） 【问题描述】
【样例输入】 【样例输出】 输入自然数n和m，输出n的所有分解和式，
7 1:7=1+1+1+1+1+1+1 分解后的每一项都不大于m。组成和式的数字自左
4 2:7=1+1+1+1+1+2 至右构成一个不降的序列，不能重复。如以下三个
3:7=1+1+1+1+3 分解式4=1+1+2；4=1+2+1;4=2+1+1 中只有第一个
4:7=1+1+1+2+2 符合要求。各组方案之间按照字典顺序输出。
5:7=1+1+1+4 【输入】输入文件factor.in中有两行，每行只有一 6:7=1+1+2+3 个正整数。第一行是n，第二行是m。
7:7=1+2+2+2 【输出】输出文件factor.out含若干行，每行先输 8:7=1+2+4 出标号，注意标号后有’:’,然后输出一个和式。
9:7=1+3+3 【数据限制】本题共有10组测试数据，
10:7=2+2+3 每组10分，共100分。100%的数据1≤n≤50，11≤≤mm≤≤nn。。 11:7=3+4
试题二：最大约数和（100分）
（源程序名：maxsum,扩展名.pas或.c或.cpp，编译后可执行程序名：maxsum.exe） 【问题描述】
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。如：输入一个数11，则可取数字4和6，可以得到约数和的最大值(1+2)+(1+2+3)=9 【输入】输入文件maxsum.in中只有一个正整数S。
【输出】输出文件maxsum.out只有一行，该行只有一个整数，为求得的最大值。 【数据限制】 【样例输入】 【样例输出】 本题共有10组测试数据，每组10分，共100分。 11 9 30%的数据, 1≤s≤10，100%的数据, 1≤s≤1000
第 1 页 共 2 页
宁波市第22届中小学生计算机程序设计竞赛决赛试题（初中组）2007年4月
试题三：单词背诵（100分）
（源程序名：letter.pas或letter.c或letter.cpp，编译后可执行程序名：letter.exe） 【问题描述】
乐乐在背单词，他发现当背诵了单词beauty 以后 ，再接着背诵单词beautiful 就会觉得容易许多。由于有很多单词要背，他希望找到一种好的背诵顺序。单词A和它的前一个单词B的最大公共前缀的长度称为背诵单词A的便利值(例如：B=’beauty’,A=’beautiful’,则A的便利值是len({A,B})=len(’beaut’)=5),我们认为一个背诵单词A的花费是它的长度(例如:’beautiful’的长度len(‘beautiful’)=9)与它的便利值之差（对于上述例子背诵A的花费为9-5=4）。请你求一个背诵顺序，使得背诵这些单词的花费总和最小。假设一开始你什么单词都不记得。
【样例输入】 【样例输出】 【输入】输入文件letter.in中有若干行。第一行只有
22 一个整数N，表示单词总数。接下来N行，每行一个单词。 5 beauty 【输出】输出文件letter.out只有一行，
beautiful 该行只有一个整数，表示求得的最小花费总和。
flower 【数据限制】本题共有10组测试数据，
man 每组10分，共100分。
dog 30%的数据, 1≤n≤100
100%的数据, 1≤n≤10000
100%的数据, 每个单词的长度在1至20之间
试题四：关路灯（100分）
（源程序名：power.pas或power.c或power.cpp，编译后可执行程序名：power.exe） 【问题描述】
某一村庄在一条路线上安装了n盏路灯，每盏灯的功率（单位时间的耗电量）有大有小。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为，先算一下左边路灯的总功率，再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，这样可以最省电。而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为1米/秒；每个路灯的位置（是一个整数，即距路线起点的距离，单位：米）；以及功率（W），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
【样例输入】 【样例输出】 【输入】输入文件power.in中有若干行。
5 3 270 第1行是两个数字n和c，分别表示路灯数和老张所处位置的路灯号； 2 10 {此时关灯顺第2行至第n+1行，每行有两个整数。其中第k+1行的第一个整数 3 20 序为34215，表示第k盏灯离路线起点的距离，第二个整数表示第k盏灯的功率。 5 20 不必输出这以上n+1行中，每行的两个整数之间都有一个空格分隔。
6 30 个关灯顺序} 【输出】输出文件power.out只有一行，该行只有一个整数，表示 8 10 求得的最少耗电量。(单位：J，1J＝1W·秒)。
【数据限制】本题共有10组测试数据，每组10分，共100分。 30%的数据, 1≤n≤20 【样例说明】有5盏灯，老张从第3100%的数据, 1≤n≤1000 盏灯开始关灯，最小耗电量 8
100%的数据, 求得的最小耗电量不大于1×10 =1*30+4*20+5*10+11*10=270
第 2 页 共 2 页