Kỳ thi học sinh giỏi tỉnh năm học 2009-2010 môn : tin học 12

SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2009-2010
 ĐẮK LẮK	 MÔN : TIN HỌC 12 - THPT	
ĐỀ CHÍNH THỨC

 	Thời gian làm bài:180 phút ( không kể thời gian giao đề)	
 Ngày thi: 22/12/2009
 Ghi chú : Đề thi này gồm 2 trang.

Bài
File bài làm
Dữ liệu vào
Kết quả
Bài 1: Dãy giảm dần -số lớn nhất 
DAYGDLN.PAS
XAU.INP
Xuất ra màn hình
Bài 2: Tính tổng 
TONG.PAS
Nhập từ phím
Xuất ra màn hình
Bài 3: Dãy số hạnh phúc 
HANHPHUC.PAS
Nhập từ phím
Xuất ra màn hình
Bài 4: Dây chuyền thông báo 
DAYCHUYEN.PAS
THONGBAO.INP 
THONGBAO.OUT


Bài 1(5,0 điểm) - Dãy giảm dần -số lớn nhất 
 Cho trước một xâu ký tự gồm toàn các chữ số. Hãy loại bỏ một số ký tự khỏi xâu sao cho các ký tự cuối cùng còn lại là một dãy giảm dần và theo đúng thứ tự đó tạo thành một số lớn nhất. Dữ liệu đọc từ file văn bản. Xuất kết quả ra màn hình.
Ví dụ:
Cho xâu X=’64562372361247120686005007710137667690’
Kết quả là: 764210

Bài 2(4,0 điểm) - Tính tổng 
 Cho dãy số thực a1, a2, …, an trong đó có cả số dương lẫn số âm (nhập từ bàn phím). 
Hãy tính tổng x1y1 + x2y2 + … + xsys. Trong đó x1, x2, …, xp là các số dương của dãy đã cho lấy theo đúng thứ tự của chúng trong dãy; y1, y2, …, yq là các số âm của dãy đã cho lấy theo thứ tự ngược lại với thứ tự của chúng trong dãy; s = min(p,q). Kết quả xuất ra màn hình.

Bài 3(4,0 điểm) - Dãy số hạnh phúc 
 Dãy số tự nhiên a1, a2, …, ak được gọi là dãy số hạnh phúc nếu nó thỏa mãn các điều kiện sau:
Dãy trên là dãy giảm dần
Với mọi i ( 1<i<=k) ai hoặc là số nguyên tố, hoặc phải là ước của một trong các số a1, a2, …ai-1.
Viết chương trình nhập vào một số N (nguyên dương) từ bàn phím và in ra một dãy số hạnh phúc dài nhất với số hạng đầu tiên là N.
Ví dụ : 
Nhập N
In ra màn hình
8
 DAY THOA MAN: 8 7 5 4 3 2 1

Bài 4(7,0 điểm) - Dây chuyền thông báo 
 Các học sinh trong một lớp học quyết định lập một dây chuyền thông báo như sau. Mỗi học sinh chọn một học sinh duy nhất khác làm người kế tiếp để truyền trực tiếp thông báo. Khi mỗi học sinh nhận được thông báo, anh ta sẽ truyền ngay cho người kế tiếp của mình. 
 Dây chuyền thông báo được gọi là tốt nếu nó thoả mãn điều kiện: Khi một học sinh A1 bất kỳ gửi thông báo cho người kế tiếp A2, A2 lại gửi cho người kế tiếp A3,..., cứ như vậy thì cuối cùng thông báo sẽ đến mọi người trong lớp kể cả người ban đầu (A1) đã phát ra thông báo. Không nhất thiết mọi dây chuyền thông báo là tốt. 
 Bài toán đặt ra là: Cho trước một dây chuyền thông báo, hãy tìm số ít nhất việc thay đổi người kế tiếp để có thể nhận được một dây chuyền thông báo tốt. 
 Dữ liệu: file văn bản THONGBAO.INP trong đó dòng thứ nhất ghi số N < 10000 là số học sinh trong lớp, các học sinh này có tên từ 1 đến N. Trong dòng tiếp theo ghi N số, số thứ i+1 là tên người kế tiếp của học sinh i. 
 Kết quả: file THONGBAO.OUT như sau: dòng thứ nhất ghi số K là số thay đổi cần tiến hành (nếu dây chuyền thông báo đã cho là tốt thì K=0). Nếu K>0, trong K dòng tiếp theo, mỗi dòng ghi hai tên học sinh, người sau là người kế tiếp mới được thay đổi của người trước. 
Ví dụ:
THONGBAO.INP
THONGBAO.OUT
10 6 9 2 7 3 1 10 3 6 9 
3 1 4 10 8 8 5


------- Hết --------

Ghi chú: Giám thị coi thi không giải thích gì thêm. 



Họ tên thí sinh: ………………………………………………………. Số báo danh: …………..




























SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2009-2010
 ĐẮK LẮK	 MÔN : TIN HỌC 12 - THPT	

ĐÁP ÁN VÀ HƯỚNG DẪN CHẤM ĐỀ CHÍNH THỨC
 
I. Phần chương trình nguồn
Bài 1(5 điểm) - Dãy giảm dần -số lớn nhất 
Uses crt;
Const nmax = 500;
Inp = ‘xau.inp’;
Type so = string[10];
Var 
F:text;
l_max:byte;
N:integer;
Opt, temp:so;
A:string;
L, pre:array[1..nmax] of integer;
Procedure nhap;
Begin
 Assign(f, inp); reset(f); readln(f,a);
 Close(f); n:=length(a);
End;
Procedure cbi;
Var I,j:integer;
Begin
 Fillchar(pre,sizeof(pre),0);
 For i:=1 to n do l[i]:=1;
 For i:=2 to n do
 For j:=1 to i-1 do
 If (a[i]=l[i]) then
 Begin
 L[i]:=l[j]+1; pre[i]:=j;
 End;
End;
Procedure tim(k:integer);
Begin
 Temp:=a[k] + temp;
 If pre[k] >0 then tim(pre[k]);
End;
Procedure xuly;
Var i:integer;
 Begin
 L_max:=0;
 For i:=1 to n do
 If l_max <l[i] then l_max:=l[i];
 Opt:=’’;
 For i:=1 to l_max do opt:=opt+’0’;
 For i:=1 to n do
 If l[i] = l_max then
 Begin
 Temp:=’’; Tim(i); writeln(temp)
 If temp>=opt then opt:= temp;
 End;
 Writeln(‘so lon nhat: ‘,opt);
End;
BEGIN
 CLRSCR;
 NHAP;
 CBI;
 XULY;
 READLN;
END.
Bài 2(4 điểm) - Tính tổng 
Var a, x, y: array[1..100] of real;
B:real;
N,p,q,I,s: integer;
BEGIN
 Write(‘ Nhap so do dai cua mang N= ‘); readln(n);
 Writeln(‘Nhap cac phan tu cua mang a tren mot dong’);
 For i:=1 to n do read(a[i]); readln;
 For i:=1 to n do if a[i]>0 then begin inc(p); x[p]:=a[i]; end;
 For i:=n downto 1 do if a[i]<0 then begin inc(q); y[q]:=a[i]; end;
 If p<q then s:=p else s:=q;
 B:=0;
 For i:=1 to s do b:=b+x[i]*y[i]
 Write(‘Tong = ‘,b:10:2);
 Readln;
END.

Bài 3(4 điểm) - Dãy số hạnh phúc 
uses crt;
var a: array[1..1000]of integer;
 i,j,k,n,d:integer;
 kt:boolean;
 function nt(n:longint):boolean;
 var i:longint;
 begin
 if n<2 then nt:=false
 else begin
 i:=2;
 while (i0) do inc(i);
 nt:=(i>sqrt(n));
 end;
 end;
BEGIN
clrscr;
write('vao n=');readln(n);
if n=2 then write(n,' ',1)
else
begin
 d:=1; a[1]:=n;
for i:= n-1 downto 1 do
 begin
 if(nt(i)) then begin inc(d);a[d]:=i;a[d]:=i;end
 else
 begin
 kt:=false;
 for j:=1 to d-1 do
 if a[j] mod i=0 then kt:=true;
 if kt then begin
 inc(d);
 a[d]:=i;
 end;
 end;
 end;
 for i:=1 to d do write(a[i],' ');
end;
readln;
END.
Bài 4(7 điểm) - Dây chuyền thông báo 
Thực chất đây là một bài toán đồ thị, nếu ta coi mỗi học sinh là một đỉnh, thì đỉnh i nối với đỉnh j khi học sinh j là người kế tiếp của học sinh i. 
Ta thấy một học sinh j có thể là người kế tiếp của rất nhiều học sinh khác, hoặc sẽ không là người kế tiếp của bất kì học sinh nào (tức là sẽ không có đỉnh i nào nối tới j). 
Gả sử ta có một học sinh jo như vậy, jo sẽ chọn cho mình một nguời kế tiếp j1, sau đó j1 lại chọn cho mình người kế tiếp j2,… quá trình này cứ tiếp diễn cho đến khi nguời kế tiếp mà jn chọn trùng với người kế tiếp của ji nào đó. Ta có thể hình dung jo…jn đã tạo nên một cây với gốc là jo (cây không phân nhánh có gốc là jo ngọn là jn). Như vậy mỗi học sinh j không được ai chọn là người kế tiếp đều tạo ra một cây, giả sử có a cây như thế. Những học sinh không tham gia ở bất kì một cây nào sẽ tạo ra những chu trình (vì mỗi học sinh của nhóm này đều được một học sinh của nhóm chọn là người kế tiếp). Giả sử có b chu trình, bây giờ ta sẽ tìm cách ghép a cây và b chu trình (ta coi chu trình là một cây khép kín, đỉnh i bất kì của nó là ngọn, đỉnh i+1 là gốc) để tạo ra một chu trình duy nhất. Rất đơn giản ta chỉ việc lấy ngọn của cây này ghép với gốc của cây kia như vậy ta cần ít nhất a+b cách thay đổi để nhận được một dây chuyền thông báo tốt. 

uses crt; const max=10001; fi=’thongbao.inp’; fo=’thongbao.out’; fu=’thongbao.luu’; var next:array[1..max] of integer; tt,ok:array[1..max] of byte; count,n:integer; f,g:text; procedure init; var i,j:integer; begin assign(f,fi); reset(f); fillchar(tt,sizeof(tt),0); readln(f,n); for i:=1 to n do begin read(f,next[i]); tt[next[i]]:=1; end; close(f); assign(f,fu); rewrite(f); count:=0; end; 
procedure get_tree(k:integer); var i,finish:integer; begin inc(count); i:=k; while ok[i]=0 do begin ok[i]:=1; finish:=i; i:=next[i]; end; writeln(f,k,’ ’,finish); 
end; 
procedure main; var i,j:integer; begin fillchar(ok,sizeof(ok),0); for i:=1 to n do if tt[i]=0 then get_tree(i); {cay} for i:=1 to n do if ok[i]=0 then get_tree(i);{chu trinh} close(f); end; 
procedure show; var start,finish,store_start,i:integer; begin assign(f,fu); reset(f); assign(g,fo); rewrite(g); writeln(g,count); read(f,store_start); for i:=1 to count-1 do begin readln(f,finish); read(f,start); writeln(g,finish,’ ’,start); end; readln(f,finish); writeln(g,finish,’ ’,store_start); close(f); close(g); end; 
begin init; main; show; end.

II. Phần hướng dẫn chấm
Bài 1(5 điểm) - Dãy giảm dần -số lớn nhất 
Xau.inp: 64562372361247120686005007710137667690
Kết quả: 764210
Bài 2(4 điểm) - Tính tổng 
Test 1: Vào: 1 -2 3 -4 5; Ra: -10
Test 2: Vào: 4 5 -2 6 -1 7 4 5; Ra: -14
…….
Bài 3(4điểm) - Dãy số hạnh phúc : Mỗi test đúng cho 1 điểm

TEST
Nhập N
Đọc ra màn hình
1
1
DAY THOA MAN: 1
2
2
DAY THOA MAN: 2 1 
3
8
DAY THOA MAN: 8 7 5 4 3 2 1
4
15
DAY THOA MAN: 15 13 11 7 5 3 2 1
5
20
DAY THOA MAN: 20 19 17 13 11 10 7 5 4 3 2 1


Bài 4(7 điểm) - Dây chuyền thông báo 
Test:
THONGBAO.INP
THONGBAO.OUT
10 6 9 2 7 3 1 10 3 6 9 
3 1 4 10 8 8 5


Chú ý: Khi chấm test của bài này, giám khảo lưu ý kết quả có thể ra khác với test đề nghị.
---- Hết ----