NOIP2009复赛普及组试题答案

第十五届全国青少年信息学奥林匹克联赛初赛试题

（ 普及组 C++语言 二小时完成 ）

● ● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一． 单项选择题 （共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）

1、 关于图灵机下面的说法哪个是正确的：

A) 图灵机是世界上最早的电子计算机。

B) 由于大量使用磁带操作，图灵机运行速度很慢。

C) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。 D) 图灵机只是一个理论上的计算模型。

2、关于计算机内存下面的说法哪个是正确的：

A) 随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随

机而不确定的。

B) 1MB内存通常是指1024*1024字节大小的内存。

C) 计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）

三个部分。

D) 一般内存中的数据即使在断电的情况下也能保留2个小时以上。

3、关于BIOS下面说法哪个是正确的：

A) BIOS是计算机基本输入输出系统软件的简称。

B) BIOS里包含了键盘、鼠标、声卡、显卡、打

题目来源：金陵中学2005-2006年第二学期信息学奥林匹克竞赛训练题

金华一中信息学奥林匹克联赛（NOIP2009）复赛模拟试题（一）

一、题目概览 中文题目名称 英文题目名称 输入文件名 输出文件名 每个测试点时限 测试点数目 每个测试点分值 比较方式 二、运行内存限制 运行内存上限 32MB 32MB 512MB 512MB 八数码 puzzle puzzle.in puzzle.out 3秒 10 10 全文比较 清扫仓库 clean clean.in clean.out 1秒 10 10 全文比较 数列 sequence sequence.in 1秒 10 10 全文比较 试题安排 arrange arrange.in 1秒 10 10 全文比较 sequence.out arrange.out

第1题 八数码

- 问题描述

大家都熟悉得不能再熟悉的八数码问题：给定一个初始状态 1 2 3 4 5 6 7 8 0

每次可以把0和与它相邻的数字交换，问最少需要多少步，可以转换到目标状态。 - 输入数据

三行三个整数，分别表示了目标状态。

- 输出数据

假如无法从初始状态到目标状态，输出一行\不含引号)，否则输出最少需要的步数。

陶陶很喜欢数学 ，尤其喜欢奇怪的数。一天，他突然发现，有的整数拥有的因子数是很有个性的，决定找到一个具有n个正因子数的最小的正整数。

例如：n=4，则m=6，因为6有4个不同正整数因子1，2，3，6；而且是最小的有4个因子的整数。 【输入文件】

仅一个数 n（1≤n≤60） 【输出文件】 仅一个数 m 【样例输入】 4

【样例输出】 6

var flag:boolean;x,t,n,i:longint; begin readln(n); x:=0;flag:=false; while not flag do begin x:=x+1;t:=0; for i:=1 to x do

if x mod i=0 then t:=t+1; if t=n then flag:=true; end;

writeln(x); end.

输入 12 输出 60 输入30 输出 720 输入 60 输出 5040 输入 45 输出 3600

2. 由文件给出n个1~30000的无序数正整数，其中1≤N≤10000,同一个正整数可能会出现多次，出现次数最多的整数称为众数，找出其中的众数及它出现的次数。输入格式：输入文件masses.in 第

1. 军方截获的信息由n（n<=30000）个数字组成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这n个数进行小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。 【输入格式】

第一行n，接着是n个截获的数字，接着一行是数字k，接着是k行要输出数的序号。

【输出格式】

k行序号对应的数字。 【输入样例】Secret.in 5

121 1 126 123 7 3 2 4 3

【输出样例】Secret.out 7 123 121

2. 有一只坏的里程表：它总是跳过数字3和数字8。也就是说，当前显示已走过两公里时，如果车子再向前走一公里，那么将显示4公里，而不是三公里（数字3跳过了）。再比如，当前是15229公里，车子再向前走一公里，显示的是15240公里，而不是15230公里。数字8也同样跳过

现在，给你里程表上显示的数字，请你告诉我车子真正走了多少公里。 输入： 15 输出： 12

3. 硬币游戏：Farmer John的奶牛喜欢玩硬币游戏，因此FJ发明了一种称为“Xoinc”的两人硬币游戏。

初始时，一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上，从堆顶数起的第I枚硬币的币值为C_i (1 <= C_i <= 100,000)。 开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走1，2，3，或4枚硬币。在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。

两个玩家都希望拿到最多钱数的硬币。请问，当游戏结束时，第一个玩家最多能拿多少钱呢？ Input

第1行：1个整数N

第2..N+1行：第i+1行包含1个整数C_i Output

第1行：1个整数表示第1个玩家能拿走的最大钱数。

Sample In

1．数字反转(reverse.cpp/c/pas)【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。【输入】输入文件名为 reverse.in。 输入共 1 行，一个整数N。

【输出】输出文件名为 reverse.out。

输出共 1 行，一个整数，表示反转后的新数。 【输入输出样例 1】reverse.in reverse.out 123 321

【输入输出样例 2】Reverse.in reverse.out -380 -83

【数据范围】-1,000,000,000 ≤ N≤ 1,000,000,000。

var

s3,s1,s2:string; n,i:integer; begin

assign(input,'reverse.in');reset(input);

assign(output,'reverse.out');rewrite(output); read(s1);

n:=length(s1); if s1[1]='-' then begin s2:='-';

f

小华的寒假作业上，有这样一个趣味填空题：

给出用等号连接的两个整数，如“1234＝127”。当然，现在这个等号是不成立的。题目让你在左边的整数中间某个位置插入一个加号，看有没有可能让等号成立。以上面的式子为例，如果写成123+4=127，这就可以了。 请你编写一个程序来解决它。

Input 只有那个不相等的式子。已知，等号两边的整数都不会超过200000000000。

Output 如果存在这样的方案，请输出那个正确的式子。如果不存在解决方案，请输出“Impossible!”（引号中的部分）。 Sample Input 1234=127 Sample Output 123+4=127 program ex1075;

var i,len,p:integer; a1,a2,b:longint;

st,st1,st2,st3:string; begin

readln(st); p:=pos('=',st);

st1:=copy(st,1,p-1); delete(st,1,p); val(st,b,x);

len:=length(st1); for i:=1 to len-1 do beg

【基础】班委确定 【试题描述】

经过紧张而激烈的选拔考试，编程班终于浮出水面，一共有k位同学幸运的入选，这k位同学个个可都是精英，才华横溢，思维敏捷。让谁做班长？让谁做学习委员？让谁做团委书记呢……？这可让班主任老师伤透了脑筋。个个都优秀，个个都能干，实在是没有办法了。抓阄吧！这个抓阄可不是普通的抓阄，老师让这k位同学围成一圈从一号位置开始顺时针报数报到m这个人就出圈（啊？猴子选大王啊！把我们当猴子啦？Of course not），出圈后就反向逆时针从下一个开始报数，报到n再出圈，然后再反向顺时针报到m出圈,反向逆时针报到n出圈……圈里的人越来越少，当还剩下5个人的时候那么这5个人就是编程班的班委。Star很想当班委，为了能够当上班委，他想请你帮忙确定哪些位置是班委的位置。 【输入描述】一行：三个整数k,m和n

【输出描述】 一行：5个数，分别为5个班委位置的号码（号码从大到小排列）。两个号码之间用一个空格隔开，最后一个号码没有空格 【输入样例】 10 3 2 【输出样例】 10 9 8 6 4

【解题提示】 样例说明： 出圈顺序为：3 1 5 2 7 剩下4 6 8 9 10 数据规模：

10%的数据 k,n,m <= 15 40%的数据 k,n,m <= 200 60%的数据 k,n,m <= 500 90%的数据 k,n,m <= 1000

100%的数据 k<=1000 n,m <= 100000 【试题来源】 常州长训班测试 var k,i,h,s,w:integer;t,z,m,n:int64; f:boolean; a:array[1..1000] of 0..1; b:array[1..5] of integer;

beg

图书馆馆长正犯愁呢，原来，有一堆的书要他整理，每本书都有一个书号（<=32767),现在他有一本书，这本书的书号为K（<=32767),现在他要找出一本书号比这本书大的书和书号比这本小的书(但都要最接近图书馆馆长已有的书号），将找到的这两本书的书号加起来，并算出加起来以后的数是否为素数

Input

第一行二个数为N,K，表示几本书以及手中书的书号（<=32767) 第二行开始有N个整数，表示这些书的书号 Output

第一行一个数，表示两本书书号加起来的和 第二行一个字符，表示和是否为素数，若是则输出\否则输出\（引号不打出） Sample Input 6 5

6 4 5 3 1 20 Sample Output 10 F

program ex1148; var n,k,i,x,s:integer;

a:array[0..32767] of integer; f:boolean; begin

readln(n,k);

fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); a[x]:=1; end; s:=0;

for i:=k+1 to 32767 do

if a[i]<>0 then begin s:=s+i;break; end; for i:=k-1 downto 1 do

if a[i]<>0 then begin s:=s+i;break; end;

1农场主的篱笆：农场主有100块1米的正方形篱笆，他想用这些篱

笆搭一个一面靠墙的长方形圈，想使圈的面积最大应如何搭建？请你邦他编程解决。

2对输入的一句子实现查找且置换的功能。如输入This is a book!↙is(查找的内容) ↙IS(替换的内容)，则输出ThIS IS a book!.

3. 输入一个'.' 结束的字串，从左至右翻译。若下一字符是数字n(0≤n≤9)，表

示后一字符重复n+1次，不论后一字符是否是数字；若下一字符是非数字字符，则表示自己。翻译后以三个字符为1组输出，组与组之间用空格分开。如输入A2B5E34G，则输出ABB BEE EEE E44 44G。

4．求全排列：生成从1到n(n<10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）： 123 132 213 231 321 312

5．公园门票每张5角，如果有2n个人排队购票，每人一张，并且其中一半人恰有５角钱，另一半人恰有１元钱，而票房无零钱可找，那么有多少种方法将这2n个人排成一列，顺次购票，使得不至于因票房无零钱可找而耽误时间？ 如输入 3 则输出 000111 001011 001101 010011 010101

6．【问题描述

图书馆馆长正犯愁呢，原来，有一堆的书要他整理，每本书都有一个书号（<=32767),现在他有一本书，这本书的书号为K（<=32767),现在他要找出一本书号比这本书大的书和书号比这本小的书(但都要最接近图书馆馆长已有的书号），将找到的这两本书的书号加起来，并算出加起来以后的数是否为素数

Input

第一行二个数为N,K，表示几本书以及手中书的书号（<=32767) 第二行开始有N个整数，表示这些书的书号 Output

第一行一个数，表示两本书书号加起来的和 第二行一个字符，表示和是否为素数，若是则输出\否则输出\（引号不打出） Sample Input 6 5

6 4 5 3 1 20 Sample Output 10 F

program ex1148; var n,k,i,x,s:integer;

a:array[0..32767] of integer; f:boolean; begin

readln(n,k);

fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); a[x]:=1; end; s:=0;

for i:=k+1 to 32767 do

if a[i]<>0 then begin s:=s+i;break; end; for i:=k-1 downto 1 do

if a[i]<>0 then begin s:=s+i;break; end;