Kì thi chọn học sinh giỏi Lớp 9 THCS năm học 2008-2009 môn Tin học

Sở Giáo Dục Đào Tạo
đề chính thức
 Tổngquan
 Kì Thi Chọn HsG LớP 9 thcs Năm Học 2008-2009
Đề thi môn :Tin học
(Thời gian 150 phút không kể thời gian giao đề)
(Đề thi gồm 2 trang )
Tên bài 
Tên fie chương trình
Tên file dữ liệu
Tênfile kết quả
thời gian
Bài 1
Xếp diêm 
hms.pas
hms.inp
hms.out
1s/test
Bài 2
Chu kỳ xâu
cyc.pas
cyc.inp
cyc.out
1s/test
Bài 3
Hoán vị có điều kiện
per.pas
per.inp
per.out
1s/test
Lập trình giải các bài toán sau:
Bài 1: Xếp diêm (4 điểm)
Với các que diêm có thể xếp được các số nguyên không âm, các chữ số thập phân có cách xếp như hình vẽ 
Bờm có N que diêm và muốn xếp diêm thành bộ số chỉ giờ dạng hh:mm:ss( chuẩn 24 giờ ) sao cho dùng hết đúng N que diêm và thời điểm biểu diễn được là muộn nhất trong ngày .
Dữ liệu (file hms.inp) : Ghi duy nhất số nguyên N (1=<n<=42)
Kết quả (file hms.out): Ghi thời điểm biểu diễn được theo định dạng hh:mm: ss(ghi số -1 nếu không có cách sắp sếp )
Ví dụ:
hms.inp
hms.out
12
11:11:11
Bài 2:Chu kì xâu(4 điểm )
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≠p P≠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áu 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 vhu kì dài nhất của hoặc xâu rỗng nếu A không có sâu chu kì .
cho một xâu S chỉ gồm các chữ cái ‘a’...’z’ hãy tính tổng dộ dài chu kì cực đại của tất cả các tiền tố của S .
Dữ liệu (cyc.inp)
Dòng 1 số nguyên N( 1<=N<=250 ) - đọ dài của xâu S 
Dòng 2 xâu S 
Kết quả (cyc.out):
Dòng 1: 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 
‘b’
‘’
‘ba’
‘’
‘bab’
‘ba’
‘baba’
‘ba’
‘babab’
‘baba’
‘bababa’
‘baba’
bababab’
‘bababa’
‘bababababa’
‘bababa’
Bài 3: Hoán vị có điều kiện ( 2 điểm)
 Hoán vị của N sốnguyên dương dầu tiên là dãy A =( a1 a2 a3 ,..., an) trong đó mỗi số nguyên 1,2,...,n dều xuất hiện đúng một lần. Một dẫycon của A là dãy nhận đươc sau khi loại bỏ 0,1,2,.. phần tử của A và dữ nguyên phần còn lại .
xét N= 4 và A=(1,4,3,2) .Độ dài của dãy con tăng dài nhất của A là 2 .A có 3 dãy con tăng độ dài là 2 là(1,4 ), (1,3); (1,2).Dộ dài của dãy con giảm dài nhất của A là 3 .A chỉ có 1 dãy con giảm dài nhất là 3 (4,3,2).
Cho N và hai số nguyên P.Q ,hãy sxác định hoán vị của N số nguyên dương đàu tiên có thứ tự từ điển nhỏ nhất thỏa mãn độ dài của dãy con tăng dài nhất , độ dài của dãy con giảm dài nhất của hoán vị đó tương ứng là P và Q .
Dữ liệu (per.inp)
Dòng 1: 3 số nguyên N, P,Q( 1<=N,P,Q <=30000 ) dữ liệu đảm bảo có nghiệm 
Dòng 2 xâu S 
Kết quả (per.out):
Dòng 1: N số nguyên là hoán vị thỏa mãn đề bài 
Ví dụ:
per.inp
per.out
4 3 2 
1 4 3 2
Giải thích ví dụ:
Còn có các hoán vị khác, chẳng hạn (2,4,3,1) cũng thỏa mãn độ dài dãy con tăng dài nhất bằng 2 , độ dài dãy con giảm dài nhất bằng 3 nhưng hoán vị (1,4,3,2) có thứ tự từ điển nhỏ nhất .
....Hết .......
Cán bộ coi thi không giải thích gì thêm
const f:array[0..9]of byte=(6,2,5,5,4,5,6,3,7,6);
	fo='hms.inp';
 go='hms.out';
var i:array[1..6]of byte;
 n,j:byte;
 f1,g:text;
 s:array[1..6]of string;
 s1,max:string;
 t1:longint;
 t2:longint absolute $00:$46c;
begin
 t1:=t2;
 assign(f1,fo);reset(f1);
 assign(g,go);rewrite(g);
	readln(f1,n);
if n<12 then write(g,-1)
else
begin
 max:='';
	for i[1]:=0 to 9 do
	for i[2]:=0 to 9 do
 for i[3]:=0 to 9 do
 for i[4]:=0 to 9 do
	for i[5]:=0 to 9 do
 for i[6]:=0 to 9 do
 	begin
 s1:='';
 for j:=1 to 6 do
 begin
	 str(i[j],s[j]);
 s1:=s1+s[j];
 end;
 if (f[i[1]]+f[i[2]]+f[i[3]]+f[i[4]]+f[i[5]]+f[i[6]]=n)and(max<s1)
	 and(s1[1]+s1[2]<='24')and(s1[3]+s1[4]<='60')and(s1[5]+s1[6]<='60')
 then max:=s1;
 end;
 if max='' then write(g,-1)
	else write(g,max[1],max[2],':',max[3],max[4],':',max[5],max[6]);
 end;
 writeln(g);
 write(g,(t2-t1)/18.2:0:9);
 close(f1);close(g);
end.
{bai 3 thi hsg 2009}
const fo='per.inp';
	 go='per.out';
var d,i,p,q,n:longint;
 f,g:text;
begin
 assign(f,fo);reset(f);
 assign(g,go);rewrite(g);
 	readln(f,n,p,q);
 if p+q-1= n then
 begin
 for i:=1 to n-q do
 begin
 write(g,i,' ');
 if i mod 255 =0 then writeln(g);
 end;
 for I:=n downto n-q+1 do
 begin
 write(g,i,' '); inc(d);
 if d mod 255 =0 then writeln(g);
 end;
 end;
 close(f);close(g);
end.
const fo='per.inp';
	go='per.out';
var i,n,p,q:longint;
	kt:boolean;
 f,g:text;
	a,b,c:array[1..10000]of integer;
procedure xuat;
var max1,max2,j:integer;
begin
max1:=0;max2:=0;
	c[1]:=1;
 for i:=2 to n do
 	begin
 c[i]:=1;
 	for j:=1 to i-1 do
 	if a[i]>a[j] then c[i]:=c[j]+1;
 if max1<c[i] then max1:=c[i];
 end;
 c[n]:=1;
 for i:=n downto 1 do
 	begin
 c[i]:=1;
 	for j:=n downto i+1 do
 	if a[i]>a[j] then c[i]:=c[j]+1;
 if max2<c[i] then max2:=c[i];
 end;
 if (max1=p)and(max2=q) then
	begin
 	for i:=1 to n do write(g,a[i],' ');
 kt:=true;
	end;
end;
procedure thu(i:integer);
var j:integer;
begin
if (i>n) then xuat
else
begin
if kt then exit
else
begin
	for j:=1 to n do
 if (b[j]=0) then
 	begin;
 	a[i]:=j;
 b[j]:=1;
 thu(i+1);
 b[j]:=0;
 end;
end;
end;
end;
begin
	assign(f,fo);reset(f);
 assign(g,go);rewrite(g);
 	readln(f,n,p,q);
 kt:=false;
	thu(1);
 close(f);close(g);
end.