第十一届全国青少年奥林匹克信息学联赛复赛普及组试题及答案
陶陶摘苹果(apple.pas/c/cpp)
【问题描述】
陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。
现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。
【输入文件】
输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。
【输出文件】
输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。
【样例输入】
100 200 150 140 129 134 167 198 200 111
110
【样例输出】
5
[参考程序]
题目讲解：简单的循环和文件操作的考察，和去年“不高兴的晶晶”有相似之处，但是比那一道题目简单。
program apple(input,output);
var
app:array[1..10] of integer;
f1,f2:text;
i,j,n:integer;
begin
assign(f1,'apple.in');
assign(f2,'apple.out');
reset(f1);
rewrite(f2);
for i:=1 to 10 do read(f1,app);
read(f1,n);
j:=0;
for i:=1 to 10 do
  if app<=n+30 then j:=j+1;
writeln(f2,j);
close(f1);
close(f2);
end.
   校门外的树（tree.pas/c/cpp）
【问题描述】
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
【输入文件】
输入文件tree.in的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
【输出文件】
输出文件tree.out包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
【样例输入】
500 3
150 300
100 200
470 471
【样例输出】
298
【数据规模】
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
[参考程序]
题目讲解：这道题目如果用常规的搜索来做的话比较复杂，另外该题目的数据量不是非常大，所以该题我们用数组来模拟实现。
program tree(input,output);
var tree1:array[0..10000] of 0..1;
  l,m,i,j,b,e:integer;
  f1,f2:text;
begin
assign(f1,'tree.in');
assign(f2,'tree.out');
reset(f1);
rewrite(f2);
read(f1,l);
for i:=0 to l do tree1:=1 ;
read(f1,m);
for i:= 1 to m do
  begin
  read(f1,b,e);
  for j:=b
for j:=b to e do
    tree1[j]:=0;
  end;
j:=0;
for i:=0 to l do if tree1=1 then j:=j+1;
write(f2,j);
close(f1);
close(f2);
end.
采药(medic.pas/c/cpp)
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
【输入文件】
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。
[参考程序]
贪心法，使用到结构类型会更加直观和方便：
program medic(input,output);
var f1,f2:text;
  med_t:array[1..100] of integer;
  med_v:array[1..100] of integer;
  med:array[1..100] of real;
  i,j,k,time,z,vale:integer;
  zz:real;
begin
assign(f1,'medic.in');
assign(f2,'medic.out');
reset(f1);
rewrite(f2);
read(f1,time,j);
for i:=1 to j do
  begin
  read(f1,med_t,med_v);
  med:=med_v/med_t;
  end;
for i:=1 to j-1 do{排序}
  for k:=i+1 to j do
  if med<med[k] then begin z:=med_t;
                    med_t:=med_t[k];
                    med_t[k]:=z;
                    z:=med_v;
                    med_v:=med_v[k];
                    med_v[k]:=z;
                    zz:=med;
                    med:=med[k];
                    med[k]:=zz;
                  end;
  vale:=0;
  for i:=1 to j do
  begin
  if med_t<=time then begin
                  vale:=vale+med_v;
                  time:=time-med_t;
                  end;
  if med_t=0 then break;
  end;
  write(f2,vale);
  close(f1);
  close(f2);
  end.
循环(circle.pas/c/cpp)
【问题描述】
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：
循环
循环长度

2
2、4、8、6
4

3
3、9、7、1
4

4
4、6
2

5
5
1

6
6
1

7
7、9、3、1
4

8
8、4、2、6
4

9
9、1
2


这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？
注意：
1． 如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。
2． 如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。
【输入文件】
输入文件circle.in只有一行，包含两个整数n（1 <= n < 10100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。
【输出文件】
输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。
【样例输入】
32 2
【样例输出】
4
【数据规模】
对于30%的数据，k <= 4；
对于全部的数据，k <= 100。
[参考程序]
应该使用高精度运算：
program circle;
type
num=record
    p:byte;
    n:array[1..100] of integer;
    end;
var
can:boolean;
code,k,i,j:integer;
st:string;
n,n2:num;
f,a:array[0..100] of num;
now:array[0..10] of num;
function multiply(x,y:num;k:byte):num;
var
  i,j:integer;
  z:num;
begin
  z.p:=x.p+y.p-1;
  if z.p>k then z.p:=k;
  fillchar(z.n,sizeof(z.n),0);
  for i:=1 to y.p do
    begin
    z.n:=z.n+x.n[1]*y.n;
    for j:=2 to x.p do
      begin
        if i+j-1>k then break;
        z.n[i+j-1]:=z.n[i+j-1]+x.n[j]*y.n;
        z.n[i+j-1]:=z.n[i+j-1]+z.n[i+j-2] div 10;
        z.n[i+j-2]:=z.n[i+j-2] mod 10;
      end;
    end;
  while (z.n[z.p]>=10)and(z.p<k) do
    begin
    inc(z.p);
    z.n[z.p]:=z.n[z.p-1] div 10;
    z.n[z.p-1]:=z.n[z.p-1] mod 10;
    end;
  z.n[z.p]:=z.n[z.p] mod 10;
  multiply:=z;
end;
function same(x,y:num;k:byte):boolean;
var
  i:integer;
begin
  same:=false;
  for i:=k downto 1 do
    if x.n<>y.n then
    exit;
  same:=true;
end;
begin
assign(input,'circle.in');
reset(input);
readln(st);
close(input);
val(copy(st,pos(' ',st)+1,length(st)-pos(' ',st)),k,code);
delete(st,pos(' ',st),length(st)-pos(' ',st)+1);
n.p:=k;
fillchar(n.n,sizeof(n.n),0);
if length(st)>k then delete(st,1,length(st)-k);
for i:=1 to length(st) do
  n.n:=ord(st[length(st)-i+1])-48;
f[0].p:=1;f[0].n[1]:=1;a[0]:=n;
f[k].p:=1;f[k].n[1]:=-1;
for i:=1 to k do
  begin
    fillchar(now,sizeof(now),0);
    now[0]:=n;n2.p:=1;n2.n[1]:=1;can:=false;
    for j:=1 to 10 do
    begin
      now[j]:=multiply(now[j-1],a[i-1],i);
      n2:=multiply(n2,a[i-1],k);
      if same(now[j],now[0],i) then
        begin
        a:=n2;
        n2.p:=1;n2.n[1]:=j;
        f:=multiply(f[i-1],n2,100);
        can:=true;
        break;
        end;
    end;
    if not can then break;
  end;
assign(output,'circle.out');
rewrite(output);
for i:=f[k].p downto 1 do write(f[k].n);
writeln;
close(output);
end.

[em5][em6][em7][em8][em9][em10][em11]