宁波市第29届中小学生程序设计竞赛复赛试题 初中组
宁波市第29届中小学生程序设计竞赛
复赛试题（初中组）
比赛时间：2014年3月29日 上午9:00-12:00
（请选手务必仔细阅读本页内容）
一． 题目概况 战马列队 queue queue queue.in queue.out 1秒 10 10 传统 马农 farmer farmer farmer.in farmer.out 1秒 10 10 传统 马语翻译 trans trans trans.in trans.out 2秒 10 10 传统 马球比赛 polo polo polo.in polo.out 1秒 10 10 传统 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 题目类型
二． 提交源程序文件名 queue.pas queue.c queue.cpp farmer.pas farmer.c farmer.cpp trans.pas trans.c trans.cpp polo.pas polo.c polo.cpp 对于pascal语言 对于C语言 对于C++语言 三． 编译命令（不包含任何优化开关） fpc queue.pas gcc –o queue queue.c -lm g++ -o queue queue.cpp -lm fpc farmer.pas gcc –o farmer farmer.c -lm g++ -o farmer farmer.cpp -lm fpc trans.pas gcc –o trans trans.c -lm g++ -o trans trans.cpp -lm fpc polo.pas gcc –o polo polo.c -lm g++ -o polo polo.cpp -lm 对于pascal语言 对于C语言 对于C++语言 四．
运行内存限制
128M 128M 128M 128M 内存上限
五． 注意事项
1、 文件名（程序名和输入输出文件名）必须使用小写。
2、 C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
第 1 页 共 5 页
宁波市第29届中小学生程序设计竞赛复赛试题 初中组
1. 战马列队 (queue.pas/c/cpp)
【问题描述】
马年到了，也到了检阅战马的时候。战马分为白色和棕色两种，一字排开，指挥官希望他的战马队列尽可能整齐好看，将相同颜色的战马放在一起。
大部分人都喜欢高头白马，因此，指挥官要求白马排在前面，棕马排在后面。现在，N匹战马都已经在广场列队。为了达到要求，指挥官可以调换任意一个位置上的战马（有充足的备用战马）。问至少调换多少匹可以达到要求。
【输入】
第一行一个整数N，表示已经排队的战马数量。 第二行一个字符串，表示当前队列从前到后战马的颜色，只包含两种字符,\表示白马，\表示黑马。
【输出】
输出一个数字，表示至少需要调换多少匹战马。
【输入输出样例1】 queue.in queue.out 5 WWWBB 【样例1解释】 已经符合白马在前，棕马在后，不需要调换。
【输入输出样例2】 queue.in 5 WBWBW 0 queue.out 2 【样例2解释】
可以把棕马都换成白马WWWWW，或者WWWBB，都是符合要求的队列，至少调换2匹。
【数据范围】
30%的数据N<=20。 70%的数据N<=500。 100%的数据N<=1000。
第 2 页 共 5 页
宁波市第29届中小学生程序设计竞赛复赛试题 初中组
2. 马农
(farmer.pas/c/cpp)
【问题描述】
在观看完战马检阅之后，来自大草原的两兄弟决心成为超级“马农”，专门饲养战马。 兄弟两回到草原，将可以养马的区域，分为N*N的单位面积的正方形，并实地进行考察，归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了。
首先，两人的马场都必须是矩形区域。同时，为了方便两人互相照应，也为了防止马匹互相走散，规定两个马场的矩形区域相邻，且只有一个交点。最后，互不认输的两人希望两个马场的收益相当，这样才不会影响他们兄弟的感情。
现在，兄弟两找到你这位设计师，希望你给他们设计马场，问共有多少种设计方案。
【输入】 第一行一个整数N，表示整个草原的大小为N*N。 接下来N行，每行N个整数A(i,j)，表示第i行第j列的单位草地的收成。 （注意：收益可能是负数，养马也不是包赚的，马匹也可能出现生病死亡等意外。）
【输出】
输出符合两人要求的草原分配方案数。
【输出输出样例1】 farmer.in farmer.out 3 1 2 3 4 5 6 7 8 9 【样例解释】 2
【数据范围】
40%的数据，N<=10。
100%的数据，N<=50, -1000 第 3 页 共 5 页 宁波市第29届中小学生程序设计竞赛复赛试题 初中组 3. 马语翻译 (trans.pas/c/cpp) 【问题描述】 随着马场的繁荣，出现了越来越多的新马种。种族之间的沟通不畅严重影响了马场的和谐。这时，科学家发明了马语翻译机器人，正好可以解决这一难题。 机器人有M种，每种机器人能完成K个马种之间的语言翻译。问，利用这些机器人，能否实现1种群和N种群的马语翻译。若可以，找到翻译过程至少需要用到多少种语言。 【输入】 第一行三个整数N，K和M，分别表示语言数，每个机器人能翻译的语言数，机器人的数量。 接下来M行，每行K个整数。表示每个机器人可以翻译的语言编号（编号从1到N）。 【输出】 输出最少转换语言的次数。如果无法完成翻译，输出-1。 【输出输出样例1】 trans.in trans.out 9 3 5 1 2 3 1 4 5 3 6 7 5 6 7 6 8 9 4 【样例解释】 1-3-6-9或者1-5-6-9 【数据范围】 40%的数据N<=100，1<=K<=20，M<=40。 100%的数据1<=N<=100000，1<=K<=1000，1<=M<=1000。 第 4 页 共 5 页 宁波市第29届中小学生程序设计竞赛复赛试题 初中组 4. 马球比赛 (polo.pas/c/cpp) 【问题描述】 在解决了马语翻译问题后，马匹数量越来越多，不少乡镇都有了数量可观的马匹，开始出现马球比赛。乡镇之间决定进行马球联赛。 联赛的赛制，主要是比赛双方的马匹数量，成了一个急需解决的问题。首先，所有乡镇都要求，本乡镇所有的马匹都必须参赛，或者都不参赛（若组队的马匹数量不是该镇马匹数量的约数，将无法参赛）。其次，在本乡镇，选出最佳球队，参加乡镇间联赛。 现在，比赛组织方希望满足所有参赛乡镇的要求，并且使得决赛的马匹尽可能多，请你设计每个球队马匹的数量，使得决赛马匹数最大。注意，决赛至少有2个队伍晋级。 【输入】 第一行一个整数N，表示想要报名参赛的乡镇。 接下来N个用空格分开的整数a(i)，表示第i个乡镇报名参赛的马匹数。 【输出】 计算出决赛最大参与的马匹数。 【输出输出样例1】 polo.in polo.out 3 1 3 6 6 【样例解释】 每个队伍3匹马，乡镇1无法参赛。乡镇2和3都可以进行比赛，决赛2个队伍，共6匹马。 【输出输出样例2】 polo.in polo.out 2 1 3 2 【样例解释】 每个队伍1匹马，因为至少需要2个队伍晋级。 【输出输出样例3】 polo.in polo.out 5 4 6 3 8 9 9 【样例解释】 每个队伍3匹马，乡镇2,3,5可以参赛。决赛3个队伍，9匹马。 【数据范围】 20%的数据2<=N<=100，1<=a(i)<=10000。 50%的数据2<=N<=20000。 100%的数据2<=N<=200000，1<=a(i)<= 2000000。 第 5 页 共 5 页