宁波市第 31 届中小学生计算机程序设计竞赛复赛试题.pdf

宁波市第 31 届中小学生计算机程序设计竞赛复赛试题（小学组） 第 1 页 宁波市第宁波市第 3131 届中小学生计算机程序设计竞赛届中小学生计算机程序设计竞赛 复赛试题（小学组）复赛试题（小学组） 比赛时间：2016 年 3 月 27 日下午 13:30-16:00 一、题目一览 试题名称 平均值 拨算盘 找画笔 射击 英文代号 average suanpan findbrush shooting 程序名 average.pas/c/cpp suanpan.pas/c/cpp findbrush.pas/c/cpp shooting.pas/c/cpp 输入文件名 average.in suanpan.in findbrush.in shooting.in 输出文件名 average.out suanpan.out findbrush.out shooting.out 内存限制 128MB 128MB 128MB 128MB 时限 1S 1S 1S 1S 分值 100 100 100 100 结果比较方 式 全文比较（过滤行末空格及文件尾的空行） 二、提交源程序文件名 对于 pascal 语言 average.pas suanpan.pas findbrush.pas shooting.pas 对于 C 语言 average.c suanpan.c findbrush.c shooting.c 对于 C+语言 average.cpp suanpan.cpp findbrush.cpp shooting.cpp 三、编译命令（不包含任何优化开关） 四、注意事项 1、 文件名（程序名和输入输出文件名）必须使用小写。 2、 C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、评测环境为 windows 4、关于竞赛中编程语言使用的其他规定参照中国计算机学会公布的关于 NOI 系列赛编程 语言使用限制的规定 对于 pascal 语言 fpcaverage.pas fpcsuanpan.pas fpc findbrush.pas fpcshooting.pas 对于 C 语言 gcc -o average average.c -lm gcc -o suanpan suanpan.c -lm gcc -o findbrush findbrush.c -lm gcc -o shooting shooting.c -lm 对于 C+语言 g+ -o average average.cpp -lm g+ -o suanpan suanpan.cpp -lm g+ -o findbrush findbrush.cpp -lm g+ -o shooting shooting.cpp -lm 宁波市第 31 届中小学生计算机程序设计竞赛复赛试题（小学组） 第 2 页 第一题、平均值 (average.pas/c/cpp) 【问题描述】 豆豆从小对数字很敏感，小学里就显露出超常的能力，老师为了防止他太过骄傲，给了 他一个可怕的难题：求一串给定整数某一段的平均值，保留 3 位小数。每个整数都是小于 231 的。老师做梦也没想到豆豆全都回答出来了，原来豆豆有一个擅长编程的朋友你。 【输入】 第一行一个整数 N(1=N=100000)，表示一串整数的个数 第二行用空格隔开的 N 个非负整数 第三行一个整数 M(1=M=100000)，表示 M 次询问 接下来 M 行，每行两个整数 i 和 j(1=i,j=N)，表示询问第 i 个到第 j 个整数的平均值， 不保证 ij 【输出】 M 行，每行一个小数，表示平均值 【样例输入 1】 5 0 25 0 23 2 1 1 5 【样例输出 1】 10.000 【样例输入 2】 3 40 60 100 2 1 3 2 3 【样例输出 2】 66.667 80.000 【数据范围】 80%的数据保证 N=1000,每个整数 Ai(0=Ai=1000000) 100%的数据保证 N 个整数和小于 263 宁波市第 31 届中小学生计算机程序设计竞赛复赛试题（小学组） 第 3 页 第二题、拨算盘 (suanpan.pas/c/cpp) 【问题描述】 对数字敏感的豆豆顺利进入了学校的珠算兴趣小组， 老师送了他们每人一个算盘， 但好 玩的算盘并不是那么容易上手的， 有很多小朋友因为嫌累纷纷退出了该兴趣小组， 豆豆觉得 人都走光了就太冷清了， 于是决定说服小朋友们留下来， 他把加法算式所需要的拨动次数算 了出来，发现其实拨动次数没有想象的那么多。 现在给你一系列加数 （正整数）， 请计算使用算盘求解时需要拨动几次， （算盘图如下， 当前表示 67） 算盘被中间的横档分为上下半区，上方只有 1 颗表示该位上的 5，靠近中间的横档就计 数 5，只要拨动它就累计一次拨动，下方的四颗每颗表示 1，靠近横档就计相应个数的 1， 下方需要拨动多颗可以合并为一次拨动。 注意：珠算里面的手法习惯是高位先算(这迎合了我们读数字的习惯） 例如 37+31，拨动方法如下图： 所以 37+31 总共需要拨动 6 次 先拨动十位 3 一 次，再拨动个位 上的 5 和 2，总 共拨动三次 十位上由 3 变成 6，上方的 5 拨 下，下方的 2 个 拨下共二次 个位上由 7 变成 8， 下方拨上一个 珠子一次 宁波市第 31 届中小学生计算机程序设计竞赛复赛试题（小学组） 第 4 页 【输入】 第一行一个整数 N(1=N=10000)，表示加数的个数 接下来 N 行，每行一个正整数，表示加数 Ai(1=Ai=Maxlongint) 【输出】 一个整数表示需要的拨动次数(假设算盘的位数足够多，不止图上的 19 位) 【样例输入 1】 2 2 3 【样例输出 1】 3 【样例输入 2】 2 26 37 【样例输出 2】 8 【样例输入 3】 2 853 947 【样例输出 3】 11 【数据范围】 30%的数据保证每个加数是 100 以内的,N=10 60%的数据保证加数和小于 231,N=100 第三题、找画笔 (findbrush.pas/c/cpp) 【问题描述】 豆豆对数字的执着， 让他在理科领域游刃有余， 但他近乎疯狂的投入也使父母有些担心， 为了让孩子能够全面发展， 决定拓宽他的学习领域， 正好家旁边有个绘画培训中心就给豆豆 报了名，学习绘画的第一天就让豆豆产生了浓厚的兴趣，还主动要求买了很多很多的画笔， 画笔有多种颜色，豆豆有一个习惯就是同种颜色的画笔就买两支，一支备用，就这样总共攒 了 N 支画笔(N 是偶数且 1N106)。 可是数字的敏感无孔不入， 豆豆脑里蹦出了一个奇怪的问题： 如果蒙上眼任意拿走一支 画笔，分析剩下的 N-1 支画笔找出拿走了哪种颜色，你能回答他吗？ 【输入】 第一行一个整数表示剩下的画笔个数就是题目描述中的 N-1 第二行 N-1 个用空格隔开的正整数 Ai(1=Ai231)，表示剩下的画笔的颜色编号 宁波市第 31 届中小学生计算机程序设计竞赛复赛试题（小学组） 第 5 页 注意：数据保证有一个画笔的颜色编号出现了一次，其余的都出现了两次注意：数据保证有一个画笔的颜色编号出现了一次，其余的都出现了两次 【输出】 一行一个整数 P，表示拿走的画笔的颜色编号。 【样例输入】 9 1 1 911 5 3 11 5 9 【样例输出】 3 第四题、射击 (shooting.pas/c/cpp) 【问题描述】 不难发现，豆豆能从很多事情中去思考数学，于是豆豆父母决定让他去练习射击，这是 项需要集中注意力的运动， 相信能够让豆豆暂时脱离数学。 学习射击的第一天就让豆豆产生 了浓厚的兴趣，射击的靶子是大饼圆，射击枪的子弹近似圆柱，为什么要圆的不能是其他的 形状呢，于是豆豆开始构思，设计了这样一个好玩的问题： N*M 的方形格子靶子，每个格子有两种状态凸或者凹（如下图浅色表示凹，深色表示 凸） 现在用一个十字横截面的子弹（填充黑色部分）去射击，被射中的小格子凹变凸，凸变 凹，子弹放大后的横截面如下图 宁波市第 31 届中小学生计算机程序设计竞赛复赛试题（小学组） 第 6 页 这种子弹最多可以覆盖 5 个格子，如图打完后，5 个格子凹凸状态发生了变化 请问最少需要几次射击使靶子中所有小格子都呈现凹的状态。 注意：子弹中心点如果打到四个角上则只会影响注意：子弹中心点如果打到四个角上则只会影响 3 个格子，如下图黑色格子表示被子个格子，如下图黑色格子表示被子 弹中心点正好击中左上角后覆盖的弹中心点正好击中左上角后覆盖的 3 个格子，如果打到除四个角的边界上，则会影响到个格子，如果打到除四个角的边界上，则会影响到 4 个格子，如下图右侧的个格子，如下图右侧的 4 个黑色格子所示，这是子弹中心点打中第个黑色格子所示，这是子弹中心点打中第 3 行第行第 6 列时的覆盖情列时的覆盖情 况。（也就是说子弹超出靶子部分不起效）况。（也就是说子弹超出靶子部分不起效） 【输入】 第一行两个用空格隔开的数字 N 和 M(1=N,M=17) 接下来 N 行描述靶子中小格子的状态，X表示凸，.表示凹。 【输出】 输出所需要的最少射击次数 注意：输入数据保证有解注意：输入数