“讯飞杯”合肥市第二十八届青少年信息学奥林匹克竞赛(小学组)解题报告

“讯飞杯”合肥市第二十八届青少年信息学奥林匹克竞赛（小学组）解题报告

胡周国

2011年11月26日 14:00-16:30 （请选手务必仔细阅读本页内容）

一、题目概况

二、注意事项

1. 考试时间为150分钟。 2. 务必看清题目，严格按照所要求的格式输入、输出。 3. 在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。

4. 每题一般有10个测试点，测试有严格的时间限制，请尽可能优化算法。 5. 命名规则：

(1)每题都规定了该题的英文名称。

(2)程序文件和数据文件的主文件名都是该题的英文名字。

(3)程序文件扩展名采用语言环境的默认扩展名。 (4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。 6. 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在文件名中含有盘符信息和任何形式的路径信息。 7. 选手在竞赛结束时应在D盘的根目录下建立以准考证号命名的文件夹，并将所完成各题的源程序文件和可执行文件拷贝到该文件夹中。

1.聪聪买书

（book.bas/book.pas/book.c）

【问题描述】

圣诞节快到了，聪聪准备给他的好朋友们买些小礼

物。当然，聪聪知道这些好朋友们都非常喜欢看漫画书，所以，聪聪就决定买些好看的漫画书送给他们。经过一段时间的调查，聪聪发现有3种买书的方式：

1 .书店现场购买：10元/本，超过5本以外的，8元/本，超过10本以外的，则6.5元/本；

2.网上购买：9元/本，超过10本，全部打8折，超过50本，则全部打六折；

3.团购：10本起团购，7元/本，达到或超过30本，则6元/本，达到或超过50本，则5元/本。

聪聪想用其中一种方式购n本书，请你帮他计算应付多少元钱？ 【输入文件】

输入文件只有1行为两个数k和n，中间以一个空格隔开 其中k表示选择的购买方式（k=1表示书店现场购买，k=2表示网上购买，k=3表示团购），n表示购买的本数(n<=200)。 【输出文件】

应付钱数（结果四舍五入保留到个位） 【输入输出样例】

【数据说明】

保证输入数据符合题目要求。

这题就是考我们对for循环的掌握和题目的理解能力。还要考虑到是这个编程软件是四舍五入，还是五舍六入。 程序如下：

var k,n,i,j:longint; s:real;

“讯飞杯”合肥市第二十八届信息学奥林匹克竞赛 begin

assign(input,'book.in'); assign(output,'book.out'); reset(input); rewrite(output); readln(k,n); if k=1 then begin

if n<=5 then s:=n*10 else

if n<=10 then s:=(n-5)*8+50 else

s:=(n-10)*6.5+90; end; if k=2 then begin s:=n*9; if n>50 then s:=s*0.6 else

小学组

“讯飞杯”合肥市第二十八届信息学奥林匹克竞赛 小学组

if n>10 then s:=s*0.8; end; if k=3 then begin

if n>=50 then s:=n*5 else

if n>=30 then s:=n*6 else

if n>=10 then s:=n*7; end;

write(s+0.1:0:0); close(input); close(output); end.

但这次是四舍五入的软件，所以只得了90分，后来听老师讲了一不管他是五舍六入还是四舍五入。那就是trunc（s+0.5)。 程序如下：

var k,n,i,j:longint; s:real; begin

assign(input,'book.in'); assign(output,'book.out'); reset(input); rewrite(output); readln(k,n); if k=1 then begin

if n<=5 then s:=n*10 else

if n<=10 then s:=(n-5)*8+50 else

s:=(n-10)*6.5+90; end; if k=2 then begin s:=n*9; if n>50 then

s:=s*0.6 else

if n>10 then s:=s*0.8; end; if k=3 then begin

if n>=50 then s:=n*5 else

if n>=30 then s:=n*6 else

if n>=10 then s:=n*7; end;

write(trunc(s+0.5)); close(input); close(output); end.

2.魅力镜片

（magic.bas/magic.pas/magic.c）

【问题描述】

由于聪聪一次性购买的书比较多，所以客气的书店老

板免费赠送一块好玩的镜片给聪聪玩。一段时间以后，聪聪发现这块镜片真的不简单：只要我们随便在纸上写一个整数，经过这个镜片一照，组成这个整数的各位数字顺序就会反转，得到一个新数，当然，神奇的不仅是这些，镜片产生的新数依然符合整数的常见情形，即除非给定的整数为零，否则反转得到的新数最高位数字不能为0。

好奇的聪聪大胆猜测这个镜片中肯定有些智能化的东

西。但是，这个东西到底是怎么实现的呢？聪聪想用计算机程序来模拟这一功能，于是，他就找到了擅长编程的你，请你帮助聪聪来解决这一问题。 【输入文件】

输入共一行，一个整数Ｎ。 【输出文件】

输出共一行，表示经镜片反转后得到的新数。 【输入输出样例1】

【输入输出样例2】

【数据范围】

-1,000,000,000≤N≤1,000,000,000。

这题就是要把他用字符串判‘-’，预处理末尾的‘0’，然后反过来输出。 程序如下：

var i,j,k:longint; a:string; begin

assign(input,'magic.in'); assign(output,'magic.out'); reset(input); rewrite(output); readln(i); str(i,a); k:=length(a); if a[1]='-' then begin

write('-'); delete(a,1,1); k:=k-1; end;

“讯飞杯”合肥市第二十八届信息学奥林匹克竞赛 while (a[k]='0')and(k<>1) do k:=k-1;

for i:=k downto 1 do write(a[i]); close(input); close(output); end.

得了100分。

这题还可以用一个著名的算法叫什么酒什麽的，哪天问个老师。 程序如下:

var i,j,k,a:longint; begin

assign(input,'magic.in'); assign(output,'magic.out'); reset(input); rewrite(output); readln(a); while a<>0 do begin

k:=k*10+a mod 10; writeln(a div 10);

小学组

a:=a div 10; end; write(k); close(input); close(output); end.

3. 好胜的明明

（prevail.bas/prevail.pas/prevail.c）

【问题描述】

明明和聪聪是好朋友，看着聪聪整天在他面前摆弄着

那块神奇的镜片，明明有点生气，总想找个机会挫挫他的锐气，但是为了不破坏他们之间的友谊，明明给聪聪出了一道难题，题目是这样的：

明明在学习英语的时候发现记单词是一件很痛苦的

事，因为这些单词都杂乱无章，于是明明决定对单词进行分类。两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等，例如“AABAC”，它和“CBAAA”就可以归为一类，而和“AAABB”就不是一类。现在有N个单词，所有单词均由大写字母组成，每个单词的长度不超过100。请你告诉明明这些单词会被分成几类。 【输入文件】

输入文件的第一行为单词个数N，以下N行每行一个单词。

【输出文件】

输出文件仅包含一个数，表示这N个单词分成的类数。 【样例输入输出】

【数据范围】

对于70%的数据满足N≤100； 对于100%的数据满足N≤550。

这题有很多的做法，我把它每个排个序，然后拍个大序，如果在一起是一样的再找，直到不一样的时，个数加1； 程序如下： var

b:array[1..550]of string; n,i,k,j:integer; d:string;

procedure q(x,y:integer;var e:string); var i,j:integer; k,t:char; begin

i:=x;j:=y;k:=e[(x+y)div 2]; repeat

while e[i]<k do i:=i+1; while e[j]>k do j:=j-1; if i<=j then begin t:=e[i]; e[i]:=e[j]; e[j]:=t; i:=i+1; j:=j-1; end; until(i>j);

if x<j then q(x,j,e); if i<y then q(i,y,e); end; begin

assign(input,'prevail.in'); assign(output,'prevail.out'); reset(input); rewrite(output); readln(n);

for i:=1 to n do begin

readln(b[i]);

q(1,length(b[i]),b[i]); end;

for i:=1 to n-1 do for j:=i to n do if b[i]<b[j] then begin d:=b[i]; b[i]:=b[j]; b[j]:=d; end; d:=b[1]; k:=1;

for i:=2 to n do if d<>b[i] then begin d:=b[i]; k:=k+1; end; if n<>0 then

write(k) else

write('0'); close(input); close(output); end.

4. 礼尚往来

（gift.bas/gift.pas/gift.c）

【问题描述】

聪聪可被明明出的题目难倒了好一会，不过，经过一番思考，聪聪还是把它解决了。作为回报，聪聪也给明明出了一个问题：平方数，或称完全平方数，是指可以写成某个整数的平方的数，即其平方根为整数的数。例如，9 = 3 × 3，它是一个平方数。聪聪很早就发现

4=2×2,9=3×3 。而2不可能分解为两个整数的乘积，但可以分解为1×1+1×1。聪聪曾经遇到过对于任意给定的正整数n把它分解成几个自然数的和的问题，在了解了平方数的知识后，聪聪想知道在所有拆分方案中，满足所有加数都是平方数的方案有多少？ 【输入文件】 一个正整数n。 【输出文件】

满足条件的方案数。 【输入输出样例1】

【输入输出样例2】

【样例说明】

5有2种分解方案，它们是：5=1×1+1×1+1×1+1×1+1×1=1×1+2×2 13有6种分解方案，它们是：

13=1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1

=1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+1×1+2×2

=1×1+1×1+1×1+1×1+1×1+2×2+2×2 =1×1+1×1+1×1+1×1+3×3 =1×1+2×2+2×2+2×2 =2×2+3×3 【数据范围】

20%的数据，1≤n≤10; 50%的数据，1≤n≤50; 80%的数据，1≤n≤800;