第十一届全国青少年奥林匹克信息学联赛复赛普及组试题

主题：第十一届全国青少年奥林匹克信息学联赛复赛普及组试题

我是严天雯 [专家分：110] 发布于 2006-12-22 18:23:00

第十一届全国青少年奥林匹克信息学联赛复赛普及组试题

采药
(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。

第十一届全国青少年奥林匹克信息学联赛复赛普及组试题

循环
(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。



第十一届全国青少年奥林匹克信息学联赛复赛普及组试题

校门外的树
(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%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。

本帖地址： http://bbs.pfan.cn/post/210810.html

回复列表（共3个回复）

沙发

zhangyuan [专家分：630] 发布于 2006-12-22 18:30:00

1：var
  a           : array[0..1000] of longint;
  t,m,i,j,x,y : longint;

begin
  assign(input,'medic.in'); reset(input);
  assign(output,'medic.out'); rewrite(output);
  readln(t,m);
  fillchar(a,sizeof(a),0);
  for i := 1 to m do begin
    readln(x,y);
    for j := t-x downto 0 do
      if a[j]+y > a[j+x] then a[j+x] := a[j]+y;
  end;
  writeln(a[t]);
  close(input); close(output);
end

2： const max=100;
type hint=array[0..max]of longint;
var st,s1,s2:string; k,ok:longint;
    a:array[0..11]of hint;
    b:array[0..9]of longint;
    circle:array[0..max]of longint;
    tot:hint;
    n,start:hint; sc,ss:hint;
    i,j,ij,l,m:longint;
procedure multi(var a:hint;b,c:hint);
var i,j,e:longint;
begin
  fillchar(a,sizeof(a),0);
  for i:=0 to k-1 do
    for j:=0 to k-1 do
      if i+j<=k-1 then inc(a[i+j],b[i]*c[j]);
  e:=0;
  for i:=0 to k-1 do begin
    a[i]:=a[i]+e;
    e:=a[i] div 10;
    a[i]:=a[i] mod 10;
  end;
end;
procedure mult(var a:hint; b:longint);
var i,e:longint;
begin
  for i:=0 to a[max] do a[i]:=a[i]*b;
  e:=0;
  for i:=0 to a[max]+1 do begin
    a[i]:=a[i]+e;
    e:=a[i] div 10;
    a[i]:=a[i] mod 10;
  end;
  if a[a[max]+1]>0 then a[max]:=a[max]+1;
end;
begin
  assign(input,'circle.in'); reset(input);
  assign(output,'circle.out'); rewrite(output);
  readln(st);
  s1:=copy(st,1,pos(' ',st)-1); delete(st,1,pos(' ',st)-1);
  s2:=st; while pos(' ',s2)>0 do delete(s2,pos(' ',s2),1);
  val(s2,k,ok);
  s2:=copy(s1,length(s1)-k+1,k);
  while length(s2)<k do s2:='0'+s2;
  for i:=1 to k do n[k-i]:=ord(s2[i])-48; n[max]:=k-1;
  start:=n; ss:=n; a[1]:=ss;
  for i:=0 to k-1 do begin
    fillchar(b,sizeof(b),0); b[a[1,i]]:=1;
    j:=2;
    while true do begin
      multi(a[j],a[j-1],ss);
      if b[a[j,i]]=0
      then begin b[a[j,i]]:=j; inc(j); end
      else begin
             sc:=ss; ij:=b[a[j,i]];
             if ij<>1
               then begin writeln(-1); close(input); close(output); halt;end;
             circle[i]:=j-1;
             for ij:=2 to j-1 do multi(ss,sc,ss);
             {a[1]:=a[b[a[j,i]]];} j:=2; break;
           end;
    end;
  end;
  fillchar(tot,sizeof(tot),0); tot[0]:=1;
  for i:=1 to k do mult(tot,circle[i-1]);
  for i:=k-1 downto 0 do if tot[i]>0 then break;
  for j:=i downto 0 do write(tot[j]);
  close(input); close(output);
end.

3：var
  t           : array[0..10000] of boolean;
  i,j,a,b,l,m : integer;

begin
  assign(input,'tree.in'); reset(input);
  assign(output,'tree.out'); rewrite(output);
  readln(l,m);
  fillchar(t,sizeof(t),true);
  for i := 1 to m do begin
    readln(a,b);
    if a > b then begin
      j := a; a := b; b := j;
    end;
    if a < 0 then a := 0;
    if b > 10000 then b := 10000;
    for j := a to b do t[j] := false;
  end;
  j := 0;
  for i := 0 to l do
    if t[i] then j := j+1;
  write(j);
  close(input); close(output);
end.

板凳

zhangyuan [专家分：630] 发布于 2006-12-22 18:36:00

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆■■■■■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆■■■■■■■■■■■■■■■☆☆☆☆
☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆■■■■■■■■■■■■■■■■■■☆☆☆☆
☆☆☆☆☆☆☆☆☆☆☆■■■■☆■■■■■■■■■■■☆☆☆☆☆☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■■■■☆■■■☆☆■■■■■☆☆☆☆☆☆☆☆☆☆☆
☆☆☆■■■■■■■■■■■■☆☆☆☆☆☆■■■■☆☆☆☆☆☆☆☆☆☆☆☆
☆■■■■■■■■■■■■■■☆☆☆☆☆☆■■■■☆☆☆☆☆☆☆☆☆☆☆☆
☆■■■■■■■■■■■■☆☆☆☆☆☆☆■■■■■■■■■■■☆☆☆☆☆☆
☆■■■■■■■■■■■■☆☆☆☆☆☆■■■■■■■■■■■■■☆☆☆☆☆
☆☆■■■■■■■■■■☆☆☆☆☆■■■■■■☆☆☆■■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆☆■■■■☆☆☆☆☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆☆■■☆☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■■☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆☆☆☆☆☆☆■■■■☆☆☆☆■■■☆☆■■■■☆☆■■■■■☆☆☆☆☆
☆☆■■☆☆☆■■■■■☆☆☆☆■■■☆☆■■■☆☆☆■■■■■☆☆☆☆☆
☆☆■■■■■■■■■■☆☆☆☆☆■■☆☆■■☆☆☆☆■■■■■☆☆☆☆☆
☆☆☆■■■■■■■■■☆☆☆☆☆☆☆☆■■■☆☆☆☆☆■■■■☆☆☆☆☆
☆☆☆☆☆■■■■■■■☆☆☆☆☆☆☆☆■■■☆■■■■☆☆☆☆☆☆☆☆☆
☆☆☆☆☆☆■■■■■■☆☆☆☆☆☆☆■■■■☆☆■■■■■☆☆☆☆☆☆☆
☆☆☆☆☆☆☆☆☆■■■☆☆☆☆☆☆■■■■■☆☆☆■■■■■■☆☆☆☆☆
☆█████████☆☆☆☆☆☆☆■■■■■■☆☆☆☆■■■■■■☆☆☆☆
☆█┏━━━━━┓█☆☆☆☆☆☆■■■■■■☆☆☆☆☆■■■■■■■☆☆☆
☆█■专业顶贴证■█☆☆☆☆☆■■■■■■☆☆☆☆☆☆☆■■■■■■■☆☆
☆█ 中国顶贴协会 █☆☆☆☆■■■■■■☆☆☆☆☆☆☆☆☆■■■■■■☆☆
☆█ ☆荣誉颁发☆ █☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆█■专业灌水证■█☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆█ ☆荣誉颁发☆ █☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆█■国家顶贴证■█☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆█┗━━━━━┛█☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
☆█████████☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

3 楼

zhangyuan [专家分：630] 发布于 2006-12-22 18:55:00

JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ■■■■■■■■■JJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ■■■■■■■■■■■■■■■JJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ■■■■■■■■■■■■■■■■■■JJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJJJJJJJJ■■■■JJ■■■■■■■■■■■JJJJJJJJJJJJJJJJJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJ■■■■■■■JJ■■■JJJJJ■■■■■JJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
JJJJJJJ■■■■■■■■■■■■JJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
JJ■■■■■■■■■■■■■■JJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
JJ■■■■■■■■■■■■JJJJJJJJJJJJJJJJ■■■■■■■■■■■JJJJJJJJJJJJJJJJJ
JJ■■■■■■■■■■■■JJJJJJJJJJJJJJJ■■■■■■■■■■■■■JJJJJJJJJJJJJ
JJJJ■■■■■■■■■■JJJJJJJJJJJJJ■■■■■■JJJJJJJ■■■■■■JJJJJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJJJ■■■■■■JJJJJJJ■■■■■JJJJJJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJJJ■■JJJJJJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■■JJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■■JJJJJJJJJJ■■■JJJJJ■■■■JJJJJ■■■■■JJJJJJJJJJJ
JJJJJ■■JJJJJJJJ■■■■■JJJJJJJJJJ■■■JJJJJ■■■JJJJJJJJ■■■■■JJJJJJJJJJJ
JJJJJ■■■■■■■■■■JJJJJJJJJJJJ■■JJJJJ■■JJJJJJJJJJ■■■■■JJJJJJJJJJJ
JJJJJJJ■■■■■■■■■JJJJJJJJJJJJJJJJJJJJJJJ■■■JJJJJJJJJJJJJ■■■■JJJJJJJJJJJ
JJJJJJJJJJJJ■■■■■■■JJJJJJJJJJJJJJJJJJJJJJ■■■JJ■■■■JJJJJJJJJJJJJJJJJJJJJJ
JJJJJJJJJJJJJ■■■■■■JJJJJJJJJJJJJJJJJJJJ■■■■JJJJJ■■■■■JJJJJJJJJJJJJJJJJJ
JJJJJJJJJJJJJJJJJJJJJ■■■JJJJJJJJJJJJJJJJJ■■■■■JJJJJJJ■■■■■■JJJJJJJJJJJ
☆█████████JJJJJJJJJJJJJJJJJJ■■■■■■JJJJJJJJJJ■■■■■■JJJJJJJJJJ
☆█┏━━━━━┓█JJJJJJJJJJJJJJJJJ■■■■■■JJJJJJJJJJJ■■■■■■■JJJJJJJ
☆█■专业顶贴证■█JJJJJJJJJJJJ■■■■■■JJJJJJJJJJJJJJJJJJ■■■■■■■JJJJJ
☆█ 中国顶贴协会 █JJJJJJJJJJ■■■■■■JJJJJJJJJJJJJJJJJJJJJJJ■■■■■■JJJJJ
☆█ ☆荣誉颁发☆ █JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
☆█■专业灌水证■█JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
☆█ ☆荣誉颁发☆ █JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
☆█■国家顶贴证■█JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
☆█┗━━━━━┛█JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
☆█████████JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第十一届全国青少年奥林匹克信息学联赛复赛普及组试题

回复列表（共3个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第十一届全国青少年奥林匹克信息学联赛复赛普及组试题

回复列表 （共3个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共3个回复）