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

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

宁波市第31届中小学生程序设计竞赛

复赛试题（初中组）

比赛时间：2016年3月27日上午9:00-12:00

（请选手务必仔细阅读本页内容）

一．题目概况 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 题目类型

二．提交源程序文件名 对于pascal语言 对于C语言 对于C++语言 eat.pas eat.c eat.cpp house.pas house.c house.cpp foreat.pas foreat.c foreat.cpp tree.pas tree.c tree.cpp 猴子吃桃 eat eat eat.in eat.out 1秒 10 10 传统 猴子拆房 house house house.in house.out 1秒 20 5 传统 猴子除草 foreat foreat foreat.in foreat.out 1秒 20 5 传统 猴子上树 tree tree tree.in tree.out 1秒 20 5 传统 三．编译命令（不包含任何优化开关） 对于pascal语言 对于C语言 对于C++语言

四．运行内存限制 内存上限 128M 128M 128M 128M 五．注意事项

1、 文件名（程序名和输入输出文件名）必须使用小写。

2、 C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、 C语言64位整型输入输出格式请用%I64d（有符号）或者%I64u（无符号）。 4、 没有其他特殊情况说明时，输入输出中任意两个整数之间用一个空格分隔。

第1页共6页

fpc eat.pas gcc -o eat eat.c -lm g++ -o eat eat.cpp -lm fpc house.pas gcc -o house house.c -lm g++ -o house house.cpp -lm fpc foreat.pas gcc -o foreat foreat.c -lm g++ -o foreat foreat.cpp -lm fpc tree.pas gcc -o tree tree.c -lm g++ -o tree tree.cpp -lm 宁波市第31届中小学生程序设计竞赛复赛试题初中组

1. 猴子吃桃 (eat.pas/c/cpp)

【问题描述】

为庆祝今年桃子丰收，猴村的猴子们举办了一次有趣的换桃子吃的游戏。n只猴子（编号为1到n）从左向右站成一排，每只猴子手上捧着某种口味的一个桃子（桃子的口味用一个小写字母表示，最多26种口味），但是猴子手上的桃子可能不是自己喜欢吃的口味。

换桃过程共进行m轮，第i（1≤i≤m）轮交换给出三个整数Li，Ri（1≤Li≤Ri≤n）和Ci，表示第i轮交换共进行Ci遍，每一遍从第Li只猴子开始依次向右边的猴子传递自己手上的桃子，即第Li只猴子传递给第Li+1只猴子，……，第Ri - 1只猴子传递给第Ri只猴子，第Ri只猴子的桃子传递给第Li只猴子。

请编程计算依次经过m轮传递后，有多少只猴子手上桃子的口味是与自己喜欢的口味相同？。

【输入】

输入共m+4行。

第1行一个整数n，表示猴子的数目。

第2行n个小写字母，依次表示第1只猴子到第n只猴子手上捧着的桃子口味。 第3行n个小写字母，依次表示第1只猴子到第n只猴子喜欢吃的桃子口味。 第4行一个整数m，表示共进行m轮交换操作。

接下来m行，第i+4行三个整数Li，Ri和Ci，表示第i轮交换共进行Ci遍，每一遍从第Li只猴子开始依次向右边的猴子传递桃子，第Ri只猴子的桃子传递给第Li只猴子。

【输出】

输出一行，一个整数，表示依次经过m轮交换后，手上桃子的口味与自己喜欢的口味相同的猴子数量。

【输入输出样例】 eat.in eat.out 7 cbcbacb ababaca 2 1 3 1 4 7 2 1 【样例解释】 输入中有7只猴子，手上捧着的桃子口味从左到右依次为“cbcbacb”，喜欢吃的桃子口味依次为“ababaca”，共进行两轮交换。

第一轮进行一遍交换，交换发生在第1只猴子到第3只猴子之间，一遍交换后的结果为“ccbbacb”。

第二轮进行两遍交换，交换发生在第4只猴子到第7只猴子之间，第一遍交换后的结果为“ccbbbac”，第二遍交换后的结果为“ccbcbba”。 经过两轮交换后，发现只有1只（第7只）猴子手上桃子的口味与自己喜欢的口味相同。

第2页共6页

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

【数据范围】

30%的数据，1≤n≤100，0≤m≤100，1?≤Ci≤1000。

100%的数据，1≤n≤10000，0≤m≤1000，1≤Li≤Ri≤n，1?≤Ci≤106。

2. 猴子拆房 (house.pas/c/cpp)

【问题描述】

猴村经过多年的发展与建设，村里面高楼林立，但为了环境整治，让村子里的房子与猴山上的环境更加和谐，猴子们打算拆掉一些房子。猴子们对拆房工人提出的拆房要求是：拆房后猴村里最高房屋的数量超过其他高度房屋数量之和，即最高房屋的数量超过房屋总数的一半。拆房的过程中，由于每幢房子结构和强度不同，需要支付给工人的钱也可能是不同的。猴子们希望用最少的钱来满足拆房要求。

特殊情况说明：当村里只剩一间房屋或者剩两间高度一样的房屋时，也算是满足拆房要求，不需要拆除。

【输入】

输入共n+1行。

第1行一个整数n，表示猴村里原有的房屋数量。

接下来n行，其中第i+1行两个整数hi和ci，分别表示第i幢房屋的高度和拆除第i幢房屋需要支付给工人的费用。

【输出】

输出一行，一个整数，表示满足拆房要求所需支付的最小费用。

【输入输出样例1】 house.in house.out 2 2 3 4 5 3 【样例1解释】 输入中共有2幢房屋，第1幢房屋的高度为2，拆房费用为3，第2幢房屋高度为4，拆房费用为5。拆除第1幢后满足拆房要求，所需支付的费用为3。

【输入输出样例2】 house.in house.out 3 2 4 2 5 1 3 第3页共6页

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

【样例2解释】 输入中共有3幢房屋，第1幢房屋的高度为2，拆房费用为4，第2幢房屋高度为2，拆房费用为5，第3幢房屋的高度为1，拆房费用为3。三幢房屋中最高高度为2，有2幢，超过房屋总数的一半，所以不需要进行拆除，支付的费用为0。

【输入输出样例3】 house.in house.out 6 3 5 3 4 1 7 1 7 4 2 4 1 10 【样例3解释】 输入中共有6幢房屋，拆除第4，5，6幢房屋后满足拆房要求，拆房后最高房屋的高度为3，有2幢，还有1幢是高度为1的房屋，需要支付的最少费用为10。满足拆房要求的方案可能不唯一，比如拆除第3，5，6幢房屋也可以。

【数据范围】

30%的数据，1≤n≤100，1≤hi≤500，1≤ci≤100。 100%的数据，1≤n≤105，1≤hi≤105，1≤ci≤500。

3. 猴子除草 (foreat.pas/c/cpp)

【问题描述】

猴子们有一个很大的花园，花园可以分成n块不同的区域（编号为1到n）。春暖花开，同时也是杂草开始生长的季节，编号为i的区域中有ai个单位面积的杂草。为了除去花园中的杂草，猴子们请了n个除草员分别给n块区域除草，每个除草员每个单位时间内可以除去1个单位面积的杂草，某个区域的杂草除完后该除草员立即停止工作。

为了提高除草的效率，希望尽快完成除草任务，猴子们买了一台除草机帮助除草员进行除草，但这台除草机在一个单位时间内仅能供一个除草员使用，使用除草机后除草员的工作效率提高到m，即该除草员每个单位时间可以除去m个单位面积的杂草（当然不使用后仍然恢复到原来的工作效率）。

现在，请你编程帮猴子们决定，怎样分配这台除草机的使用对象才能使完成所有除草任务的时间最短？

【输入】

输入共2行。

第1行两个整数n和m，表示花园中共有n块待除草的不同区域和除草员使用除草机时

第4页共6页

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

的工作效率为m。

第2行n个整数，第i个整数ai表示第i块区域中有ai个单位面积的杂草。

【输出】

输出一行，一个整数，表示完成所有除草任务所需的最短时间。

【输入输出样例】 foreat.in foreat.out 3 4 2 3 5 2 【样例解释】

输入中有3块需要除草的区域，每块区域杂草的面积依次为2，3，5个单位面积。如果使用除草机在单位时间内能除4个单位面积的草。

完成所有除草任务最少需要2个单位时间。方案可能不唯一，比如：

方案一：在第一个单位时间内，除草机给2号区域的除草员使用，第一个单位时间结束时各区域依次还有1，0，4个单位面积的杂草。在第二个单位时间内，除草机给3号区域的除草员使用，第二个单位时间结束时各区域依次还有0，0，0个单位面积的杂草，即经过2个单位时间后所有的杂草被除尽。

方案二：在第一个单位时间内，除草机给3号区域的除草员使用，第一个单位时间结束时各区域依次还有1，2，1个单位面积的杂草。在第二个单位时间内，除草机给2号区域的除草员使用，第二个单位时间结束时各区域依次还有0，0，0个单位面积的杂草，即经过2个单位时间后所有的杂草被除尽。

【数据范围】

30%的数据，1≤n≤1000，0≤ai≤10000。

599

100%的数据，1≤n≤10，0≤ai≤10，1≤m≤10。

4. 猴子上树 (tree.pas/c/cpp)

【问题描述】

在猴村有一条笔直的山路，这条山路很窄，宽度忽略不计。有n只猴子正站在山路上静静地观望今天来参加比赛的各位同学。用一个正整数Xi表示第i只猴子所站位置，任意两只猴子的所站位置互不相同。在这条山路的m个位置上种着一些高大的树木，正整数Yj表示第j棵树木所在的位置，任意两棵树的位置互不相同。

正当猴子们聚精会神的欣赏各位高超的编程技能时，一只老虎大摇大摆的走了过来。猴子们吓得直冒冷汗，第一反应就是找一棵大树爬上去，这样就能避免被老虎咬死或者吃掉（不考虑老虎上树问题）。

在位置a的猴子跑到在位置b的大树上，需要消耗的能量为 |a-b|（即a-b的绝对值）。为了尽可能有效利用这些大树避难，每棵大树上至少要有一只猴子。

请编程计算n只猴子全部上树最少需要消耗多少能量？

第5页共6页

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

【输入】

输入共4行。

第1行一个整数n，表示猴子的数量。

第2行n个整数，第i个整数Xi表示第i只猴子所在的位置。 第3行一个整数m，表示大树的数量。

第4行m个整数，第j个整数Yj表示第j棵大树所在的位置。 【输出】

输出一行，一个整数，表示n只猴子全部上树最少需要消耗的能量。

【输入输出样例1】 tree.in tree.out 3 1 4 5 2 3 8 6 【样例1解释】

输入中共有3只猴子，所在的位置分别为1，4，5。山路旁边有两棵大树，位置在3和8。第1只猴子爬上在位置3的大树，消耗的能量为|1-3|=2，第2只猴子也爬上在位置3的大树，消耗的能量为|4-3|=1。因为要保证每棵树上至少有一只猴子，所以第3只猴子爬上在位置8的大树，消耗的能量为|5-8|=3。所以3只猴子全部上树最少需要消耗的能量为6。

【输入输出样例2】 tree.in tree.out 3 3 1 10 2 8 3 4 【数据范围】

3

30%的数据1≤n≤500，1≤Xi ,Yi≤10。

9

100%的数据1≤n≤5000，1≤m≤n，1≤Xi ,Yi≤10。 提示：请关注本题内存限制大小。

第6页共6页

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

【输入】

输入共4行。

第1行一个整数n，表示猴子的数量。

第2行n个整数，第i个整数Xi表示第i只猴子所在的位置。 第3行一个整数m，表示大树的数量。

第4行m个整数，第j个整数Yj表示第j棵大树所在的位置。 【输出】

输出一行，一个整数，表示n只猴子全部上树最少需要消耗的能量。

【输入输出样例1】 tree.in tree.out 3 1 4 5 2 3 8 6 【样例1解释】

输入中共有3只猴子，所在的位置分别为1，4，5。山路旁边有两棵大树，位置在3和8。第1只猴子爬上在位置3的大树，消耗的能量为|1-3|=2，第2只猴子也爬上在位置3的大树，消耗的能量为|4-3|=1。因为要保证每棵树上至少有一只猴子，所以第3只猴子爬上在位置8的大树，消耗的能量为|5-8|=3。所以3只猴子全部上树最少需要消耗的能量为6。

【输入输出样例2】 tree.in tree.out 3 3 1 10 2 8 3 4 【数据范围】

3

30%的数据1≤n≤500，1≤Xi ,Yi≤10。

9

100%的数据1≤n≤5000，1≤m≤n，1≤Xi ,Yi≤10。 提示：请关注本题内存限制大小。

第6页共6页

本文来源：https://www.bwwdw.com/article/c43o.html