合肥市第二十九届青少年信息学奥林匹克竞赛(小学组)试题及部分答案(6页).doc

-合肥市第二十九届青少年信息学奥林匹克竞赛(小学组)试题及部分答案-第 6 页“讯飞杯”合肥市第二十九届信息学奥林匹克竞赛   小学组 “讯飞杯”合肥市第二十九届青少年信息学 奥林匹克竞赛（小学组）试题及部分答案（请选手务必仔细阅读本页内容） 一、题目概况 中文题目名称源程序名输入文件名输出文件名满分测试点数目是否有部分分内存限制每个测试点时限素数number10010否128M1秒换座位shuffle10010否128M1秒楼梯stair10010否128M1秒二、注意事项1. 考试时间为 150 分钟。2. 务必看清题目，严格按照所要求的格式输入、输出。3. 在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。4. 每题有 10 个测试点，测试有严格的时间限制，请尽可能优化算法。5. 命名规则：(1)每题都规定了该题的英文名称。(2)程序文件和数据文件的主文件名都是该题的英文名字。(3)程序文件扩展名采用语言环境的默认扩展名。(4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in 和.out。6. 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在文件名中含有盘符信息和任何形式的路径信息。7. 选手在竞赛结束时应在 D 盘的根目录下建立以准考证号命名的文件夹，并将所完成各题的源程序文件和可执行文件拷贝到该文件夹中。合肥  20121201 第  1  页/共  3 页 “讯飞杯”合肥市第二十九届信息学奥林匹克竞赛   小学组 1.素数(number)【问题描述】期中考试刚刚结束，聪聪是班上的学习委员，可是这次数学成绩班上好多同学都考了满分，聪聪只考了 98 分，就错在一道求素数的题目上，题目是这样的：已知 N 和 M 两个正整数，求 N 至 M 之间（包括 N 和 M）有多少个素数。聪聪觉得很懊恼，他决定必须研究清楚这个问题。由于聪聪今年刚加入学校的计算机兴趣班，于是他决定利用编程来解决这个问题，你能帮助他吗？【输入文件】输入文件共一行：两个正整数数 N 和 M，中间以一个空格隔开。【输出文件】输出文件一个正整数：表示 N 至 M 之间（包括 N 和 M）的素数个数。【输入输出样例】3 7【数据说明】1NM32767。32.换座位（shuffle）【问题描述】 在你的帮助下，聪聪很快解决了这个问题，信心又回来了。老师为了奖励聪聪这种知难而进的精神，决定把今年的庆祝少先队建队 63 周年纪念活动中的游戏项目交给聪聪来策划。 聪聪可高兴了，他召集了班上的少先队员一起来讨论，最终确定了这样一个游戏：班上共有 2N 个少先队员，开始时每个少先队员坐在自己的板凳上排成一队，由聪聪开始击鼓，每次击鼓开始时，前 N 个同学坐到第 2、4、2N 个板凳上，后 N 个同学坐到第 1、3、2N-1 个板凳上，击鼓结束时坐错或者还没有坐到对应板凳上的同学就要接受惩罚表演一个节目。聪聪不断的击鼓然后停顿后又击鼓，同学们都觉得这个游戏很好玩，但是当游戏结束时，同学们傻眼了，由于每位同学的板凳都差不多，他们找不到自己的板凳了。这次聪聪反应特别快，他说经过一定次数的换座位，每位同学一定能回到自己的板凳的。那么这个次数最少是多少呢？你会计算吗？【输入文件】输入共一行，一个正整数 N。【输出文件】输出文件一个正整数，每位同学都回到自己板凳的最少换座位次数。【输入输出样例】10【数据范围】1N10,000。6合肥  20121201 第  2  页/共  3 页 “讯飞杯”合肥市第二十九届信息学奥林匹克竞赛   小学组 这个游戏启发了聪聪，他想：如果积木底盘无限大，当积木数很多时，能摆放的情况就有很多很多，你能计算出有 N 个积木时按照上述规则能摆放出多少种情况吗？【输入文件】输入文件为一个正整数 N（N3），表示积木个数。【输出文件】输出文件一个正整数，表示能摆放出的情况数。【样例输入输出】5【数据范围】对于 40%的数据满足 N10；对于 80%的数据满足 N100；对于 100%的数据满足 N200。2合肥  20121201 第  3  页/共  3 页 答案：program shuffle(input,output);var a,b:array1.20000 of integer; n,i,j,t:integer;begin readln(n); for i:=1 to 2*n do ai:=i; repeat j:=j+1; for i:=1 to 2*n do begin if ai<=n then ai:=ai*2 else ai:=(ai-n)*2-1; end; until a1=1; writeln(j);end. 【问题描述】聪聪的游戏全校同学都很喜欢，老师表扬了聪聪。放学回家以后，发现小表弟在家，妈妈告诉表弟：“聪聪哥哥特别会玩游戏，你让聪聪哥哥陪你玩啊！，小表弟就拿出他的积木”让聪聪陪他玩，聪聪开始不想在家陪表弟，他想和同学出去玩呢，可是妈妈说，如果陪表弟玩开心了，周末就带他去游乐场。听了这话，聪聪就跟妈妈保证，一定好好陪小表弟玩。聪聪一边拿着表弟的积木，一边在想，平常的游戏表弟都玩腻了，有什么新的好玩的呢。不一会聪聪就想到了，小表弟的这组积木有个底盘，是由很多方格组成的，积木中正好有一些与方格大小相同的正方形积木，聪聪和小表弟一起按如下规则将这些正方形积木摆放在底盘上：底盘的每一竖行方格组成一列，必须从最左边的一列开始摆放，每列从最下面的方格开始连续摆放积木，底盘至少要放两列，后一列放的积木数至少比前一列多一个。下图为 5个积木所能摆放的出的情况。聪聪一边教表弟一边摆出不同积木数的各种情况。3. 楼梯（stair）