宁波市第30届中小学生程序设计竞赛初中组复赛试题

1、宁波市第30届中小学生程序设计竞赛复赛试题 初中组宁波市第30届中小学生程序设计竞赛复赛试题（初中组）比赛时间：2015年3月28日 上午9:00-12:00（请选手务必仔细阅读本页内容）一 题目概况中文题目名称羊羊整除羊羊吃草羊羊修路羊羊列队英文题目名称diveatroadqueue可执行文件名diveatroadqueue输入文件名div.ineat.inroad.inqueue.in输出文件名div.outeat.outroad.outqueue.out每个测试点时限1秒1秒1秒1秒测试点数目10201010每个测试点分值1051010题目类型传统传统传统传统二 提交源程序文件名对于pa

2、scal语言div.paseat.pasroad.pasqueue.pas对于C语言div.ceat.croad.cqueue.c对于C+语言div.cppeat.cpproad.cppqueue.cpp三 编译命令（不包含任何优化开关）对于pascal语言fpc div.pasfpc eat.pasfpc road.pasfpc queue.pas对于C语言gcc o divdiv.c -lmgcc o eat eat.c -lmgcc o road road.c -lmgcc o queue queue.c -lm对于C+语言g+ -o div div.cpp -lmg+ -o eat e

3、at.cpp -lmg+ -o road road.cpp -lmg+ -o queue queue.cpp -lm四 运行内存限制内存上限128M128M128M256M五 注意事项1、 文件名（程序名和输入输出文件名）必须使用小写。2、 C/C+中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。1. 羊羊整除(div.pas/c/cpp)【问题描述】羊年到了，村长开始教小羊学习Pascal语言，刚开始学习四则运算。村长在白板上写下两个整数16和3，问小羊们，有16只羊，平均分到3个羊村，每个羊村分到的数量必须相同，这个分配的数量最大是多少？小羊们很快就得到了答案，

4、每个羊村分到5只，有1只羊就只能落单了。村长在白板上写下5。没错，这个就是Div(整除)的用法！为了检验小羊们是否掌握了整除运算，村长要求小羊们轮流从白板上任意选取两个不同的数，由大数整除小数，若所得结果没有出现在白板上，就将该值写在白板上。直到小羊们再也找不到没出现过的整数。虽然这样上课很锻炼小羊们的运算能力，但是课堂时间有限。为了控制课堂时间，村长想要知道，根据当前白板上的数字，最终白板上会出现几个数字？现在请你帮他编写一个程序快速计算一下吧！【输入】第一行一个整数N，表示当前白板上出现的整数个数。第二行N个整数，中间用空格分隔，表示当前在白板上的数字，保证每个数字都不相同。【输出】输出一

5、个整数，表示最终白板上数字的个数。【输入输出样例1】div.indiv.out216 34【样例1解释】选择16和3，写下5；选择5和3，写下1；共16，3，5，1，四个整数。【输入输出样例2】div.indiv.out317 2 15【样例2解释】选择17和2，写下8；再选择8和2，写下4；共17，2，8，4，1，五个整数。【数据范围】50%的数据，N<=50；100%的数据，N<=100，1<=ai<=100。2. 羊羊吃草(eat.pas/c/cpp)【问题描述】小羊们上完课后，纷纷到草场上吃草。而羊村现在正在进行特色示范羊村检查，领导们想看看羊村的草场。羊村的草

6、场是连续分布的，每块草场上都有数量不等的羊在吃草。领导们想要查看连续若干个草场，但是又不想看到超过T只羊。而村长希望领导们多看看羊村的风貌，尽可能多参观几个草场。现在，请你帮村长决定，带领导们去参观哪一段草场，满足领导和村长的要求。【输入】第一行一个整数N和T，表示羊村共有多少个连续草场，以及领导们希望看到羊数量的最大值。第二行N个整数，两个整数间用一个空格分开，第i个数ai表示第i个草场上有ai只羊在吃草。编号从1到N。【输出】输出一行，共两个数，表示参观的起点编号和终点编号，中间用空格分开。走的方向总是从编号小的到编号大的。另外，若有长度相同的可能性，输出起点编号较小的答案。数据保证至少有

7、答案存在。【输入输出样例1】eat.ineat.out5 106 3 2 1 72 4【样例解释】要满足连续个总和不超过10，有3+2+1和2+1+7两种可能性，优先输出2到4个草场。【数据范围】30%的数据，1<=N<=100;60%的数据，1<=N<=1000;100%的数据，1<=N<=100000, 0<=ai<=109，0<=T<=231-1。3. 羊羊修路(road.pas/c/cpp)【问题描述】经过特色示范羊村检查，检查组觉得羊村的道路需要重修，破败的道路，会影响到小羊们上学的安全。村长组织施工队，开始丈量距离，规划施

8、工方案，已经得到了若干建筑物间修建道路的可行方案，共有N个建筑物，和M条可选道路。这些路保证可以将N个建筑相连。最终方案中，羊村打算修建全球最豪华的全大理石道路，道路可以双向通行，且一体成型，路中无缝隙。为了达到这个设计要求，就必须自建大理石工厂！大理石工厂建造的难度在于，必须根据其需要生产最大长度的大理石来设计。工厂可以生产出不超过其设计极限的任意长度的大理石。例如，设计长度为100的工厂，可以生产100、90等长度的大理石，但是不能生产长度为101的大理石。羊村的预算有限，希望你能帮忙规划出一个修路方案，使得工厂的设计规模尽可能小，且可以保证其能生产的大理石可以连通所有羊村的建筑。求出工厂

9、的最小设计规模。【输入】第一行两个整数N和M，N表示羊村中的建筑数量，M表示可以修建的道路数量。接下来M行，每行三个整数Ai，Bi和Ci，表示从建筑Ai，到建筑Bi，可以修建一条长度为Ci的道路。注意，建筑编号从1到N，两个建筑之间可能有多条道路。【输出】输出大理石工厂的最小设计规模。【输入输出样例】road.inroad.out3 31 2 1002 3 1011 3 99100【样例解释】只要修建1到2，以及1到3的道路，就可以使得3个建筑相互连通，且最大值只有100，只需要建造设计规模为100的大理石工厂，就可以生产出长度为100和99的大理石。【数据范围】30%的数据N<=10，

10、N-1<=M<=100。100%的数据1<=N<=2000，N-1<=M<=10000，1<=Ai，Bi<=N，1<=Ci<=1000000000。4. 羊羊列队(queue.pas/c/cpp)【问题描述】在修建完新路后，小羊们总算可以安心入学了。今年是羊年，新入学的小羊特别多。老师们打算将N只小羊分成M个班级，每个班至少有1只羊。如何分班成了老师们最头疼的事情，因为开学典礼上，村长就要看到小羊们列队的情况。每个班的小羊都排成一排，站在草场上。村长希望队列中羊的高度尽可能整齐，村长对队列的不整齐度有自己的要求。例如队列中共有t只羊，高度依次为A1，A2，At。那么不整齐度为：(|A1-A2|+|A2-A3|+|At-1-At|)2。即相邻两只羊高度差之和的平方。而总体的不整齐度，就是各班不整齐度之和。现在，请你帮助老师们设计一下，如何分班，如何列队，才能使M个班级的不整齐度之和最小。【输入】第一行两个整数N和M，分别表示共有N只小羊，要被分成M个班级。第二行N个整数，表示每只小羊的高度Ai。【输出】输出最小的不整齐度之和，结果保证不会超过231-1。【输出输出样例】queue.inqueue.out4 24 1 3 22【样例解释】分成两班，4和3一个班，1和2一个班，不管怎么排，两个班的不整齐度都是1，不整齐度