《第20届高中决赛试题》由会员分享，可在线阅读，更多相关《第20届高中决赛试题（8页珍藏版）》请在金锄头文库上搜索。
1、宁波市第 20 届中小学生计算机程序设计竞赛决赛试题(高中组)第 1 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页宁波市第宁波市第 20 届中小学生计算机程序设计竞赛决赛试题届中小学生计算机程序设计竞赛决赛试题(高中组)学校 姓名 准考证号 注意： 1、考试时间 120 分钟，满分 120 分；2、请仔细阅读“考生须知”中的有关规定；3、上机时如有问题应及时举手请监考老师解决；4、编程开始后，不要关机，完成后请监考老师验收后再离开。高中高中 1： 数的划分数的划分(20 分分)（源程序名：源程序名：gz1.pas，可执行文件名：，可执行文件名：gz1.
2、exe）（输入文件名：（输入文件名：gz1.in，输出文件名：，输出文件名：gz1.out）问题描述将整数 n 分成 k 份，且每份不能为空，任意两种分法不能相同(不考虑顺序)， 例如:n=7,k=3,下面三种分法被认为是相同的。 1，1，5； 1，5，1； 5，1，1；问有多少种不同的分法。输入文件只包含一行：即两个整数 n 和 k(6n200，2k6)，中间用空格间隔。输出文件: 只有一个整数，为不同的分法种数。输入输入/输出样例输出样例 输入： 7 3 输出：4 （ 4 种分法为：1,1,5；1,2,4；1,3,3; 2,2,3 ）宁波市第 20 届中小学生计算机程序设计竞赛决赛试题(高
3、中组)第 2 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页高中高中 2： 方格取数方格取数 (30 分分)（源程序名：源程序名：gz2.pas，可执行文件名：，可执行文件名：gz2.exe）（输入文件名：（输入文件名：gz2.in，输出文件名：，输出文件名：gz2.out）问题描述设有 NN 的方格图（N8） ，我们将其中的某些方格中填入正整数，而其他的方格中 则放入数字 0。如下图所示（见样例）： 向右A12345678100000000200130060030000700040001400005021000400600150000070140000
4、00向下800000000B某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。 在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0） 。此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。 输入文件：输入的第一行为一个整数 N（表示 NN 的方格图） ，接下来的每行有三个整 数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 表示输入结束。 输出文件：只需输出一个整数，表示 2 条路径上取得的最大的和。 输入输入/输出样例输出样例 输入 82 3 132 6 63 5 74 4 145 2 215 6
5、 46 3 157 2 140 0 0 输出：67宁波市第 20 届中小学生计算机程序设计竞赛决赛试题(高中组)第 3 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页高中高中 3： 四色图问题四色图问题(30 分分)（源程序名：源程序名：gz3.pas，可执行文件名：，可执行文件名：gz3.exe）（输入文件名：（输入文件名：gz3.in，输出文件名：，输出文件名：gz3.out）问题描述在绘制区域地图时，要求以国家为单位着色，所有相邻国家着不同颜色。试编写一程序 实现如下功能：使用至多四种不同颜色对地图进行涂色(每块涂一种颜色)，要求相邻区域的 颜色互
6、不相同，输出所有可能的涂色方案总数。 例如：下图由 7 个区域组成的地图，所有可能的涂色方案总数为 768。输入文件：共有 n+1 行，第一行是一个整数 n,表示有 n 个区域，接下来的 n 行依次表 示 nn 矩阵中每行有 n 个 0 或 1，其中 1 表示两区域相邻，0 表示不相邻。 输出文件：只有一个整数，表示所有可能的涂色方案总数。 输入/输出样例输入：70 1 0 0 1 0 11 0 0 1 0 1 00 0 0 1 0 0 10 1 1 0 0 1 11 0 0 0 0 0 10 1 0 1 0 0 01 0 1 1 1 0 0输出：768宁波市第 20 届中小学生计算机程序设计
7、竞赛决赛试题(高中组)第 4 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页高中高中 4： 公共汽车调度问题公共汽车调度问题(40 分分)（源程序名：源程序名：gz4.pas，可执行文件名：，可执行文件名：gz4.exe）（输入文件名：（输入文件名：gz4.in，输出文件名：，输出文件名：gz4.out）问题描述有一个人在某个公共汽车站上，从 12:00 到 12:59 观察公共汽车到达本站的情况，该 站被多条公共汽车线路所用，他依次记下公共汽车到达本站的时刻。 1.在 12:00 到 12:59 期间，同一条线路上的公共汽车以相同的时间间隔到站； 2.
8、时间单位用“分”表示，从 0 到 59； 3.每条公共汽车线路至少有两辆车到达本站； 4.不同公共汽车线路的首次到站时间和到站的时间间隔都有可能相同。 请为公共汽车线路编一个调度表，目标是：公共汽车线路数目最少的情况下，使公共汽 车到达本站的时刻满足输入数据的要求。例如： 汽车编号12345678到达时间0351314142125那就可能存在这样一个解，由以下三条汽车线路组成：线路一：0，14（间隔时间为 14）线路二：3，14，25（间隔时间为 11）线路三：5，13，21（间隔时间为 8）输入文件共有二行：第一行为一个整数 n（表示到达站点的公共汽车数量） ，第二行有 n 个整数，表示公共
9、汽车到站时间。输出文件：只需输出一个整数，表示最少的公共汽车线路数目。输入输入/输出样例输出样例 输入：80 3 5 13 14 14 21 25输出：3宁波市第 20 届中小学生计算机程序设计竞赛决赛试题(高中组)第 1 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页宁波市第宁波市第 20 届中小学生计算机程序设计竞赛决赛试题测试数据届中小学生计算机程序设计竞赛决赛试题测试数据(高中组)试题一试题一(20 分分)（程序名：（程序名：GZ1-准考号末准考号末 2 位）位）输入文件输入文件 n k 输输 出出 分值分值 得分得分 Gz11.in 7232
10、Gz12.in 204643 Gz13.in 1005382254 Gz14.in 20055834645 Gz15.in 200641320966 试题二试题二 (30 分分)（程序名：（程序名：GZ2_准考号末准考号末 2 位）位）输入文件输入文件输输 出出分值分值得分得分Gz21.in3 1 1 10 1 3 5 2 2 6 2 3 4 3 1 8 3 2 2 0 0 0306Gz22.in7 1 3 2 1 4 3 2 3 3 3 3 3 5 5 4 6 5 4 7 3 2 7 5 4 0 0 0256Gz23.in8 1 1 13606宁波市第 20 届中小学生计算机程序设计竞赛决赛
11、试题(高中组)第 2 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页1 3 7 1 8 14 2 2 1 2 4 2 4 3 5 5 5 4 6 2 6 7 8 16 0 0 0Gz24.in8 1 1 1 1 8 1 2 2 2 2 7 2 3 4 3 3 5 3 4 4 3 4 5 3 7 2 2 7 7 2 8 1 1 8 8 1 0 0 0186Gz25.in8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0676试题三试题三(30 分分)（程序名：（程序名：GZ3_准考号末准
12、考号末 2 位）位）输入文件输入文件输输 出出分值分值得分得分Gz31.in7 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 17686宁波市第 20 届中小学生计算机程序设计竞赛决赛试题(高中组)第 3 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0Gz32.in6 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 029
13、286Gz33.in7 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 08646Gz34.in6 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 038886Gz35.in10 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1
14、0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 022686试题四试题四(40 分分)（程序名：（程序名：GZ4_准考号末准考号末 2 位）位）输入文件输入文件输输 出出分值分值得分得分Gz41.in8 0 3 5 13 14 14 21 25310宁波市第 20 届中小学生计算机程序设计竞赛决赛试题(高中组)第 4 页 参考答案竞赛后将在宁波市计算机学会网站www.nbcai.org上公布 共 4 页Gz42.in5 3 8 12 15 21210Gz43.in17 0 2 5 8 10 14 14 20 22 23 26 30 32 36 38 40 41410Gz44.in8 0 5 10 20 20 30 35 401810
