Hội thi học sinh giỏi duyên hải bắc bộ

thanhkhoeo · 10 Tháng hai 2012

Bài 1 ( 6 điểm) : Chu kì của xâu Tên chương trình : CYC.PAS
Một xâu P được gọi là tiền tố của xâu A nếu tồn tại xâu B sao cho xâu PB (ghép B vào sau P) bằng xâu A. Một tiền tố P của A được gọi là tiền tố thực sự nếu P khác rỗng và P khác A.
Xâu Q được gọi là xâu chu kì của xâu A nếu Q là một tiền tố thực sự của A và A là tiền tố của xâu QQ. Chẳng hạn, abab và ababab là hai xâu chu kì của xâu abababa. Chu kì cực đại của A là xâu chu kì dài nhất của A ( nếu A không có xâu chu kỳ thì coi như độ dài chu kỳ cực đai = 0 ).
Cho một xâu S chỉ gồm các chữ cái in thường (‘a’..‘z’), hãy tính tổng độ dài chu kì cực đại của tất cả các tiền tố của S.
Dữ liệu vào từ tệp CYC.INP
• Dòng 1: số nguyên N (độ dài xâu S , 1≤N≤ 250)
• Dòng 2: xâu S
Kết quả ra tệp CYC.OUT ghi số nguyên kết quả
Ví dụ :
cyc.inp cyc.out
8
babababa 24
Giải thích ví dụ
Tiền tố Chu kì cực đại Độ dài
‘b’ ‘’ 0
‘ba’ ‘’ 0
‘bab’ ‘ba’ 2
‘baba’ ‘ba’ 2
‘babab’ ‘baba’ 4
‘bababa’ ‘baba’ 4
‘bababab’ ‘bababa’ 6
'babababa’ ‘bababa’ 6
Tổng 24

Bài 2 (7 điểm ) : Trả tiền mua hàng Tên chương trình : MONEY.PAS
Một người đi mua hàng với giá trị của hàng là M đồng .Trong túi người đó có N loại tiền với các mệnh giá T1, T2, . . . TN, mỗi loại có một số lượng tương ứng S1, S2, . . . SN. Hỏi người đó có thể trả đúng số tiền mua hàng được không (không tính khả năng trả thừa tiền rồi người bán hàng trả lại ..), nếu có thể hãy đưa ra cách trả giúp cho người đó. (Biết M, N, Ti, Si nguyên dương; M ≤ 10000 ; N≤10 ; Si ≤ 10 ; Ti ≤10000 ; Ti > Ti+1 )
Dữ liệu vào từ tệp MONEY.INP
- Dòng 1: chứa số N và M
- Dòng 2: chứa N số Ti
- Dòng 3: chứa N số Si.
Kết quả ra tệp MONEY.OUT
- Dòng 1 ghi tổng số tờ phải trả trong trường hợp có cách trả tiền , nếu không thì ghi 101
- Trường hợp có cách trả thì dòng 2 ghi N số với ai là số tờ tiền phải trả tương ứng với loại tiền có mệnh giá Ti , nếu có nhiều cách trả với tổng số tờ ít nhất như nhau thì ghi ra dãy có thứ tự từ điển lớn nhất ( các số ghi cách nhau một dấu cách ).
Ví dụ 1:
MONEY.INP
5 91
13 9 6 3 1
4 10 4 6 5
MONEY.OUT
9
4 4 0 1 0
( ở đây còn cách trả 9 tờ nữa là
4 3 2 0 0 nhưng có thứ tự từ điển
nhỏ hơn …)
Ví dụ 2:
MONEY.INP
5 100
60 9 5 3 1
4 2 2 3 2
MONEY.OUT
101

Bài 3 (7 điểm): Tập số hữu tỷ Tên chương trình : CANTOR.PAS
Georg Cantor là nhà toán học nổi tiếng và một trong những chứng minh quan trọng của ông là việc chỉ ra rằng lực lượng của tập số hữu tỷ đúng bằng lực lượng tập số tự nhiên. Cơ sở của việc chứng minh đó là sơ đồ sau:
1/1
2/1 1/2
3/1 2/2 1/3
4/1 3/2 2/3 1/4
5/1 4/2 3/3 2/4 1/5
6/1 5/2 4/3 3/4 2/5 1/6
...
Trong sơ đồ trên, mỗi số hữu tỷ dương tương ứng với một số nguyên dương , số đầu tiên là 1/1, số thứ 2 là 1/2, số thứ 3 là 2/1, số thứ 4 là 3/1, số thứ 5 là 2/2, số thứ 6 là 1/3 , số thứ 7 là 1/4 , … ( đếm theo đường zíc zắc )
Yêu cầu: Cho một số nguyên dương , hãy tìm phân số có số thứ tự tương ứng với nó theo sơ đồ trên.
Dữ liệu vào từ tệp CANTOR.INP
Gồm 1 dòng ghi số nguyên dương n ( n≤1017 )
Kết quả ra tệp CANTOR.OUT
Gồm 1 dòng ghi phân số có thứ tự n dưới dạng a/b.
Ví dụ :

CANTOR.INP
3
7
9
11
14
1000000 1009/406
CANTOR.OUR
2/1
1/4
3/2
5/1
2/4

hoangha8394 · 11 Tháng hai 2012

Đây hình như là đề thi khối 10 năm ngoái thì phải.
Thằng em học dưới mình 1 lớp chỉ vì khai báo thiếu cái int64 mà mất cái giải nhất =((

quanghero100 · 11 Tháng hai 2012

Bài 3: Mọi người xem thử

Mã:

uses crt;
const fi='d:\cantor.inp';
      fo='d:\cantor.out';
var n:longint;
    f1,f2:text;
procedure xuli(n:longint);
var k,i,j:longint;
 begin
  k:=3;
  i:=2;
  j:=1;
  if n=1 then writeln(f2,'1/1');
  if n=2 then writeln(f2,'1/2');
  if n=3 then writeln(f2,'2/1');
  if n>3 then
  begin
     repeat
       if k<n then
         begin
           inc(i);
           inc(k);
           if k=n then break;
         end;
      if (i>1) and (k<n) then
         begin
           repeat
             dec(i);
             inc(j);
             inc(k);
           until (k=n) or (i=1);
         end;
      if k<n then
         begin
           inc(j);
           inc(k);
           if k=n then  break;
         end;
      if (j>1) and (k<n) then
         begin
           repeat
             dec(j);
             inc(i);
             inc(k);
           until (k=n) or (j=1);
         end;
    until k=n;
    writeln(f2,i,'/',j);
  end;
 end;
begin
 assign(f1,fi);
 reset(f1);
    assign(f2,fo);
    reset(f2);
    rewrite(f2);
    while not eof(f1) do
       begin
         readln(f1,n);
         xuli(n);
       end;
   close(f2);
 close(f1);
end.

quanghero100 · 12 Tháng hai 2012

Bài 1 đây mọi người test thử hí

Mã:

uses crt;
var s1,s2:string;
    a:array[1..100] of string;
    k:integer;
    f1,f2:text;
 function tiento(s1,s2:string):boolean;
  var kt:boolean;
   begin
     kt:=false;
     if copy(s2,1,length(s1))=s1 then kt:=true;
     tiento:=kt;
   end;
 function ttthucsu(s1,s2:string):boolean;
  var kt:boolean;
   begin
     kt:=false;
     if (tiento(s1,s2)=true) and (s1<>s2) and (s1<>'') then kt:=true;
     ttthucsu:=kt;
   end;
 function chuki(s1,s2:string):boolean;
  var kt:boolean;
   begin
     kt:=false;
     if (ttthucsu(s1,s2)=true) and (tiento(s2,s1+s1)=true) then kt:=true;
     chuki:=kt;
   end;
 procedure xuli;
  var i,t,j:integer;
   begin
    t:=0;
    for i:=1 to length(s2) do
      begin
        inc(k);
        a[k]:=copy(s2,1,i);
      end;
    for i:=3 to k do
      begin
        j:=length(a[i])+1;
        repeat
          dec(j);
          s1:=copy(a[i],1,j);
        until chuki(s1,a[i])=true;
        t:=t+length(s1);
      end;
    writeln(f2,t);
   end;
begin
 assign(f1,'D:\CYC.INP');
  reset(f1);
   readln(f1,s2);
  assign(f2,'D:\CYC.OUT');
   reset(f2);
    rewrite(f2);
    xuli;
  close(f2);
 close(f1);
 end.

Tìm kiếm

Tìm kiếm

Hội thi học sinh giỏi duyên hải bắc bộ

thanhkhoeo

hoangha8394

quanghero100

quanghero100