模拟题解题参考

信息学奥赛复赛模拟题解题参考

第一题 交通流量测试（traffic） ............................................................................................ 1 第二题 走楼梯（strair） .......................................................................................................... 5 第三题 津津的储蓄计划（save） .............................................................................................. 6 第四题 合唱队形 (chorus) ........................................................................................................ 9 第五题 均分纸牌（card） ......................................................................................................... 10

第一题 交通流量测试（traffic） 【问题描述】

为调查统计车辆流量，在路边设置了一台车辆探测器。探测信号用线路连接到计算机。凡有一辆车通过时，探测器自动传送一个数字信号1给计算机；探测器中有个时钟，统计开始时，启动时钟，此后每一秒钟自动传送一个数字信号2给计算机；统计结束时，探测器向计算机发送一个数字为0的终止信号。编写一个程序，以处理探测器送来的这一系列信息，并输出下列结果：

(1)进行了多长时间的调查统计； (2)记录到的车辆总数；

(3)在车辆之间最长的时间间隔是多少。 【输入文件】

输入文件traffic.in包括一行整数（有且仅有最后一个整数为0），分别表示探测器发送给计算机的数字信号。 【输出文件】

输出文件traffic.out包括三行，每行一个整数，分别表示调查统计的时间、记录到的车辆总数以及车辆间的最长时间间隔。 【样例输入】

1 1 2 2 1 1 1 1 2 1 2 2 2 2 2 1 1 1 1 1 2 0 【样例输出】 9 12 5

[解]这些结果，要等到探测结束时才能统计完成。在程序中要使用到如下变量： 过往车辆数，以标识符unms表示； 时间以seconds表示； 时间间隔以inter表示；

最长时间间隔以longest表示；

探测器信号以sig表示，分别为：1 车辆信号、2 计时信号、0 结束统计信号。

现在，我们开始学习用伪代码描述程序的开发过程。解决所提问题的程序设计过程，可表示如下：

第一步 把任务写成一个“总语句”： program begin

信息学奥赛复赛模拟题解题参考 第 2 页 共 12 页

用车辆探测器统计车辆流量 end．

第二步 把任务分解为几个子任务(功能块)： program begin

对有关变量赋以初值，准备开始统计；

当送来的信号不是结束信号时，反复处理探测器送来的信号； 输出统计结果。 end．

信息学奥赛复赛模拟题解题参考 第 3 页 共 12 页

第三步 进一步细化各个子任务： program begin

若干个赋初值的赋值语句和读语句 while送来信号不是结束信号时 do begin

if是车辆信号

then处理车辆信号 else if是计时信号

then处理计时信号；

送下一个信号 end；

输出统计结果的若干写语句。 end．

第四步 到目前这一步，赋初值与输出统计结果这两个子目标，已完全可以具体到

用语句描述了，但while语句的循环体，尚须进一步细化到用语句描述。 program begin

若干赋初值的赋值语句和读语句 {变量初始化} while sig<>0 do begin

if sig=1 then begin

车辆数nums的值增1; if inter>longest

then inter的值取代longest的当前值;

inter置零; end

else if sig=2 then begin

seconds的值增1,inter的值增1; 送下一个信号; end end；

输出统计结果的若干写语句; end．

信息学奥赛复赛模拟题解题参考 第 4 页 共 12 页

第五步 最终程序 program traffic; {

过往车辆数，以标识符unms表示； 时间以seconds表示； 时间间隔以inter表示；

最长时间间隔以longest表示；

探测器信号以sig表示，取值分别为：1 车辆信号、2 计时信号、0 结束统计信号。 } var

unms,secondS,inter,longest,sig:integer; f1,f2:text; begin

assign(f1,'traffic.in'); assign(f2,'traffic.out'); reset(f1); rewrite(f2); unms:=0; secondS:=0; inter:=0; longest:=0; read(f1,sig); while sig<>0 do begin

if sig=1 then begin

unms:=unms+1;

if inter>longest then longest:=inter; inter:=0; end

else if sig=2 then begin

seconds:=seconds+1; inter:=inter+1; end; read(f1,sig); end;

writeln(f2,seconds); writeln(f2,unms); writeln(f2,longest); close(f1); close(f2); end.

信息学奥赛复赛模拟题解题参考 第 5 页 共 12 页

当然细化过程分多少步并无定规，可因问题的简繁或程序员编程技术的熟练程度而异。但不难看出，上述第一步做的是表达用户需求，第二步是进行总体设计(也称初步设计，即划分功能模块，并确定模块之间的组成关系，因此，也就是程序的结构设计)。第三、四步的工作则是模块设计(或称详细设计，是程序模块内的过程设计)，第五步就是编码工作。以上“五步”也称“五级”或“五个阶段”，各种称乎意思都大致相同。

回头看一看，想一想之后，你可能提出异议：“编写这样几十行的短小程序，完全可以一气呵成。还要分四步、五步，进行什么分解、求精，不是多此一举吗?”是的，你的意见有一定道理，但你别忘记我们是在进行“方法学习”。是把小型程序当作大型程序的雏形。这样“小题大作”，目的是通过小型程序的设计，模拟大型程序系统的开发步骤、原理、方法。 著名计算机科学家格里斯(D．Gries)说过：“只有学会有效地编写小程序的人，才能学习有效地编写大程序。”其中的道理显而易见，不用多作解释。连小文章都写不好的人，难以设想他居然能完成优秀的宏篇巨著。

第二题 走楼梯（strair） 【问题描述】

某个楼梯共有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，也可以一步上3阶，编一程序计算共有多少种不同的走法。 【输入文件】

输入文件strair.in包括一个整数n，分别楼梯的台阶级数。 【输出文件】

输出文件strair.out包括一个整数，表述走台阶的方法总数。 【样例输入】 3

【样例输出】 4

[解]首先模拟一下走楼梯的方法，如图所示： n=1时，方法f(n)=1； n=2时，方法f(n)=2； n=3时，方法f(n)=4；

n=4时，方法f(n)=f(3)+f(2)+f(1)=7；

同理可以推导出通项公式 f(n)=f(n-1)+f(n-2)+f(n-3)；

信息学奥赛复赛模拟题解题参考 第 6 页 共 12 页

有了这个通项公式（递推表达式），可以很容易设计递归的方式解决问题。参考代码如下： program strair; var

n:integer; f1,f2:text;

function f(n:integer):integer; begin

if n=1 then f:=1; if n=2 then f:=2; if n=3 then f:=4;

if n>=4 then f:=f(n-1)+f(n-2)+f(n-3); end;

begin

assign(f1,'strair.in'); assign(f2,'strair.out'); reset(f1); rewrite(f2); read(f1,n);

writeln(f2,f(n)); close(f1); close(f2); end.

第三题 津津的储蓄计划（save） 【问题描述】

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。因此津津制定了一个储蓄计划：每个月的月

信息学奥赛复赛模拟题解题参考 第 7 页 共 12 页

初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2007年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2007年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。 【输入文件】

输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。 【输出文件】

输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2007年年末津津手中会有多少钱。 【样例输入1】 290 230 280 200 300 170 340 50 90 80 200 60

【样例输出1】 -7

【样例输入2】 290 230 280 200 300 170 330 50 90 80

信息学奥赛复赛模拟题解题参考 第 8 页 共 12 页

200 60

【样例输出2】 1580

[解]这是近年分区联赛当中最简单的题，算法也很简单：模拟法。 每个月把津津手上的钱加上妈妈给的300元，再减去预算，得到当前手中的钱，假如这个钱的值是负数（出现亏损），那么就输出负的月数，接着算出存入的钱，并且将手中的钱减去。如此往复，直到最后按要求输出结果或者中间已经停止。参考代码如下： program save; var

a:array[1..12] of integer; have,s,x,temp,i:integer; f1,f2:text; b:Boolean; begin

assign(f1,'save.in'); assign(f2,'save.out'); reset(f1); rewrite(f2);

for i:=1 to 12 do read(f1,a[i]); b:=True; x:=0; have:=0; s:=0;

for i:=1 to 12 do begin

temp:=have+300-a[i]; if temp<0 then begin x:=i; b:=false; end else begin

s:=s+temp div 100*100; have:=temp mod 100; end; end;

if not b then writeln(f2,-x) else writeln(f2,trunc(s*1.2)+have); close(f1); close(f2); end.

信息学奥赛复赛模拟题解题参考 第 9 页 共 12 页

第四题 合唱队形 (chorus) 【问题描述】

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2„，K，他们的身高分别为T1，T2，„，TK， 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入文件】

输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 【输出文件】

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 【样例输入】 8

186 186 150 200 160 130 197 220 【样例输出】 4

【数据规模】

对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。

[解]假设每个人为中间身高最高的人（可以用循环枚举），要使出列的人数最小，即这个人的左边和右边都有尽可能多的人。此人左右两边分别满足严格上升和下降的关系，且人数最多。

首先求出最长连续序列，从左向右看升序的数目，左边升序的最大值记做up[i]；同样循环枚举，右边降序的最大值记做down [i]。

然后，枚举每个人i，有 ki=up[i]+down[i]-1，记录下最大的k值，minans=n-maxki 就是出列的最小数目。

参考代码如下： program chorus; var

t:array[0..101] of longint;

up,down:array[0..101] of longint; n,i,j,k,max:integer; f1,f2:text; begin

assign(f1,'chorus.in'); assign(f2,'chorus.out'); reset(f1);

信息学奥赛复赛模拟题解题参考 第 10 页 共 12 页

rewrite(f2); readln(f1,n); //读入升身高数据

for i:=1 to n do read(f1,t[i]); t[0]:=0; t[n+1]:=0;

for i:=0 to n+1 do up[i]:=0; for i:=0 to n+1 do down[i]:=0; //左侧升序最大 for i:=1 to n do begin

max:=1;

for j:=0 to i-1 do

if (t[j]//左侧降序最大

for i:=n downto 1 do begin

max:=1;

for j:=n+1 downto i+1 do

if (t[j]//求出满足条件的最大k k:=0;

for i:=1 to n do

if k第五题 均分纸牌（card） 【问题描述】

有 N 堆纸牌，编号分别为 1，2，„, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。

移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4，4 堆纸牌数分别为：

信息学奥赛复赛模拟题解题参考 第 11 页 共 12 页

① 9 ② 8 ③ 17 ④ 6 移动3次可达到目的：从 ③ 取 4 张牌放到 ④ （9 8 13 10）—> 从 ③ 取 3 张牌放到 ②（9 11 10 10）—> 从 ② 取 1 张牌放到①（10 10 10 10）。 【输入文件】

输入文件card.in 包含两行正整数，第一行只有一个正整数N表示纸牌堆数（1<=N<=100），第二行包含N个用空格隔开的正整数（在1到10000之间），分别表示每堆纸牌的初始张数。 【输入文件】

输出文件card.out 包含一个正整数，表示所有堆均达到相等时的最少移动次数。

【输入样例】 4

9 8 17 6 【输出样例】

3

[解]如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！因为这样可以简化思考难度。例题中，平均张数为(9+8+17+6)/4=10，原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数。我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边（第2堆）-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。

也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，尽管方向不一样，但是步数是一样的。

如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，则无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。

本题有三点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是要过滤掉0（不是所有的0，如-2，3，0，-1中的0是不能过滤的）；三是负数张牌也可以移动，这是辩证法思维。 参考代码如下： program card; const maxn=100; var

i,j,n,step:integer; ave:longint;

a:array[1..maxn]of integer; f1,f2:text;

信息学奥赛复赛模拟题解题参考 第 12 页 共 12 页

begin

assign(f1,'card.in'); assign(f2,'card.out'); reset(f1); rewrite(f2); readln(f1,n); ave:=0; step:=0;

for i:=1 to n do begin

read(f1,a[i]); inc(ave,a[i]); end;

ave:=ave div n;

for i:=1 to n do a[i]:=a[i]-ave; i:=1; j:=n;

while a[i]=0 do inc(i);{过滤左边的0} while a[j]=0 do dec(j);{过滤右边的0} while (iinc(a[i+1],a[i]);{将第i堆牌移到第i+1堆中去} a[i]:=0;{第i堆牌移走后变为0} inc(step);{移牌步数计数}

inc(i);{对下一堆牌进行循环操作}

while a[i]=0 do inc(i);{过滤移牌过程中产生的0} end;

writeln(f2,step); close(f1); close(f2); end.