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

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2010-2011
 ĐẮK LẮK	 MÔN : TIN HỌC 12 - THPT	
ĐỀ CHÍNH THỨC
	 (Thời gian: 180 phút, không kể thời gian giao đề)	
	 Ngày thi: 12/11/2010
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: Tìm dãy con 
DAYCON.PAS
Nhập từ phím
Xuất ra màn hình
Bài 2: Vòng số nguyên tố
VONGNGUYENTO.PAS
VONG.INP
VONG.OUT
Bài 3: Đếm số ô vuông
OVUONG.PAS
NGANG.INP 
DOC.INP
Xuất ra màn hình
Bài 1: (6,0 điểm) - Tìm dãy con 
 Cho mảng gồm n số nguyên (có thể âm, dương và không nhất thiết khác nhau) a[1], a[2], ,a[n] và một số nguyên S. hãy tìm tất cả các dãy con chỉ số 1≤ i1<i2<<ik ≤ n thỏa mãn a[i1] + a[i2] ++ a[ik] = S.
Ví dụ: Dãy 6 số a = (1,7,2,9,3,5) ; s = 8 cho kết quả: 
Daycon1: 1 7
Daycon2: 3 5
Daycon3: 1 2 5
Bài 2: (7,0 điểm) - Vòng số nguyên tố 
 Một vòng tròn chứa 2n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ 1 đến 2n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến 2n mỗi số vào một vòng tròn nhỏ sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số 1. 
 Dữ liệu: Vào từ file văn bản VONG.INP chứa số nguyên dương n (1 < n < 10) 
Kết quả: Ghi ra file văn bản VONG.OUT: 
• Dòng đầu tiên ghi số lượng các cách điền số tìm được (k). 
• Dòng thứ i trong số k dòng tiếp theo ghi các số trong các vòng tròn nhỏ bắt đầu từ vòng tròn nhỏ 1 đọc theo thứ tự của các vòng tròn nhỏ 
VÍ DỤ:
VONG.INP 
3 
VONG.OUT 
2 
1 4 3 2 5 6 
1 6 5 2 3 4 
Bài 3: (7,0 điểm) - Đếm số ô vuông 
 Cho một bảng gồm NxN điểm nằm trên các mắt lưới ô vuông (3 ≤ N ≤ 100). các điểm kề nhau trên một hàng hay một cột có thể được nối với nhau bằng một đoạn thẳng hoặc không được nối. Các đoạn đó sẽ tạo ra các ô vuông trên bảng. 
Ví dụ: với bảng sau đây thì N = 4 và có 3 ô vuông:
 Trên mỗi hàng có thể có nhiều nhất N-1 đoạn thẳng nằm ngang và có tất cả N hàng như vậy. Tương tự như vậy có tất cả N-1 hàng các đoạn thẳng nằm dọc và trên mỗi hàng có thể có nhiều nhất N đoạn.
 Để mô tả người ta dùng hai mảng nhị phân: một mảng ghi các đoạn thẳng nằm ngang kích thước N x (N-1), và một mảng ghi các đoạn nằm dọc kích thước (N-1) x N. Trong mảng dùng số 1 để mô tả đoạn thẳng nối giữa 2 điểm, còn số 0 miêu tả giữa 2 điểm không có đoạn thẳng nối. Trong ví dụ trên thì:
 ma trận ngang ma trận dọc 
1
0
1
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
0
1
1
0
 Cho trước ma trận ngang và ma trận dọc. Hãy lập trình đếm số ô vuông trên bảng. 
Dữ liệu vào được nhập từ các tập tin: ngang.inp và doc.inp. 
+ Tập tin ngang.inp có N dòng, N-1 cột là các số 0 hoặc 1, mỗi số được ghi cách nhau ít nhất một dấu cách.
+ Tập tin doc.inp có N-1 dòng và N cột là các số 0 hoặc 1, mỗi số được ghi cách nhau ít nhất một dấu cách.
Xuất kết quả ra màn hình.
------- Hết --------
Thí sinh không được sử dụng tài liệu.
Giám thị không giải thích gì thêm.
Họ và tên thí sinh............ Số báo danh....
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH NĂM HỌC 2010-2011
 ĐẮ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(6 điểm) - Tìm dãy con 
program daycon;
uses crt;
const size=100;
var
 a:array[1..size] of integer;
 x:array[1..size] of integer;
 n,s,smin,smax:integer;count:word;
 name:string;
procedure init;
var i:integer;
begin
 write('nhap n = ');readln(n);
 for i:=1 to n do
 begin
 write('a[',i,']= ');readln(a[i]);
 end;
 write('S= ');readln(s);
 smin:=0;smax:=0;
 for i:=1 to n do
 begin
 if a[i]<0 then smin:=smin+a[i]
 else smax:=smax+a[i];
 end;
 count:=0;
end;
procedure printresult;
var i:integer;
begin
 inc(count);write('Day ',count,':':3);
 for i:=1 to n do
 if x[i]=1 then write(a[i]:3);
 writeln;
end;
procedure try(i,smin,smax:integer);
var j:byte;s1,s2:integer;
begin
 for j:=0 to 1 do
 begin
 s1:=smin; s2:=smax;
 if j=0 then
 if a[i]<0 then s1:=s1-a[i]
 else s2:=s2-a[i]
 else
 if a[i]<0 then s2:=s2+a[i]
 else s1:=s1+a[i];
 if (s1<=s) and (s<=s2) then
 begin
 x[i]:=j;
 if i=n then printresult else try(i+1,s1,s2);
 end;
 end;
end;
BEGIN
 clrscr;
 INIT; TRY(1,SMIN,SMAX);
 readln;
END.
Bài 2(7 điểm) -Vòng số nguyên tố 
program Circle; 
const
 InputFile = 'VONG.INP';
 OutputFile = 'VONG.OUT';
 max = 9;
 Count: array[2..9] of LongInt = (2, 2, 4, 96, 1024, 2880, 81024, 770144);
var
 X: array[1..2 * max] of Byte;
 Free: array[1..2 * max] of Boolean;
 Accept: array[1..2 * max, 1.. 2 * max] of Boolean;
 n, m: Byte;
 Time: Longint absolute $0000:$046C;
 OldTime: Longint;
 f: Text;
 BackCount: Longint;
procedure Enter;
var
 f: Text;
begin
 Assign(f, InputFile); Reset(f);
 Readln(f, n);
 m := n SHL 1;
 Close(f);
end;
function P_Number(X: Byte): Boolean;
var
 b: Boolean;
 i: Byte;
begin
 b := X > 1;
 for i := 2 to Trunc(Sqrt(X)) do b := b and (X mod i 0);
 P_Number := b;
end;
procedure Init;
var
 i, j: Byte;
begin
 FillChar(Free, m, True);
 for i := 1 to m do
 for j := 1 to m do Accept[i, j] := P_Number(i + j);
 BackCount := Count[n];
end;
procedure WriteResult;
var
 i: Byte;
 begin
 Dec(BackCount, 2);
 for i := 2 to m do Write(f, X[i],' ');
 Write(f, X[1]);
 Writeln(f);
 Write(f, '1 ', X[1]);
 for i := m downto 3 do Write(f, ' ', X[i]);
 Writeln(f);
end;
procedure Try(i: Byte);
var
 j: Byte;
begin
 if odd(i) then j := 2 else j := 3;
 repeat
 if BackCount = 0 then Exit;
 if Free[j] and Accept[X[i - 1], j] then
 begin
 X[i] := j;
 if i m then
 begin
 Free[j] := False;
 Try(i + 1);
 Free[j] := True;
 end
 else
 if Accept[j, X[1]] then WriteResult;
 end;
 Inc(j, 2);
 until j > m;
end;
procedure TryAll;
var
 i, j: Byte;
begin
 X[2] := 1; Free[1] := False;
 for i := 2 to m do
 for j := i + 1 to m do
 if Accept[1, i] and Accept[j, 1] then
 begin
 X[1] := j; X[3] := i;
 Free[i] := False; Free[j] := False;
 Try(4);
 Free[i] := True; Free[j] := True;
 end;
end;
BEGIN
 OldTime := Time;
 Enter;
 Assign(f, OutputFile); Rewrite(f);
 Writeln(f, Count[n]);
 Init;
 TryAll;
 Close(f);
 Writeln('Time: ', (Time - OldTime)/18.2:1:2);
END.
Bài 3(7 điểm) - Đếm số ô vuông 
Uses crt; 
Const Ngang = 'ngang.inp';
 Doc = 'doc.inp';
 Max = 100;
 n: integer = 0;
 count: integer =0;
Var f1,f2:text; 
 o,i,j:integer; 
 a,b,c:array[1..max] of boolean; 
BEGIN 
 clrscr; 
 Assign(f1,ngang); Assign(f2,doc); 
 Reset(f1); Reset(f2); 
 While not eoln(f1) do 
 begin 
 Read(f1,o); 
 Inc(n); 
 If o=1 then a[n]:=true 
 else a[n]:=false 
 end; 
 Readln(f1); 
 for i:= 1 to n do 
 begin 
 for j:= 1 to n do 
 begin 
 Read(f1,o); 
 If o=1 then b[j]:=true 
 else b[j]:=false; 
 end; 
 Readln(f1); 
 for j:=1 to n+1 do 
 begin 
 Read(f2,o); 
 If o=1 then c[j]:=true 
 else c[j] := false 
 end; 
 Readln(f2); 
 for j:=1 to n do 
 begin 
 If (a[j] and b[j] and c[j] and c[j+1]) then 
 inc(count); 
 end; 
 a:=b; 
 end; 
 Close(f1); Close(f2);
 Write('Co ', count, ' hinh vuong');
 Readln; 
END.
II. Phần hướng dẫn chấm
Bài 1: (6,0 điểm) - Tìm dãy con 
Mỗi test 2 điểm
Test1: Dãy 6 số a=(1,7,2,9,3,5) ; s=8 cho kết quả: 
Daycon1: 1 7
Daycon2: 3 5
Daycon3: 1 2 5
Test2: 
Dãy 5 số a=(1,2,4,6,3) ; s=8 cho kết quả: 
Daycon1: 2 6
Daycon2: 1 4 3
Test3: Dãy 7 số a=(1,7,2,9,3,5) ; s= 22 cho kết quả: 
Daycon1: 2 3 6 4 8 -1
Daycon2: 1 3 6 4 8
Bài 2: (7.0 điểm) -Vòng số nguyên tố 
Test1 1 điểm, 2 test sau mỗi test 3 điểm.
TEST1
VONG.INP 
3 
VONG.OUT 
2 
1 4 3 2 5 6 
1 6 5 2 3 4 
TEST2
VONG.INP 
 4 
VONG.OUT 
4 
1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2
Test 3
VONG.INP 
2
VONG.OUT 
2
1 2 3 4
1 4 3 2
Bài 3: (7,0 điểm) - Đếm số ô vuông 
Test1: 2điểm, các test sau mỗi test 1 điểm
Ngang.inp
Doc.inp
1
1
1
1
1
1
1
0
0
1
0
0
0
1
1
1
0
0
1
0
0
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
Có 7 ô vuông
Test 2
Ngang.inp
Doc.inp
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
1
1
1
1
1
1
1
0
1
0
1
0
1
0
0
0
0
0
Có 5 ô vuông
Test 3:
Ngang.inp
Doc.inp
1
1
1
0
0
0
0
1
1
1
0
0
Có 0 ô vuông
Test 4:
Ngang.inp
Doc.inp
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Có 9 ô vuông
Test 5:
Ngang.inp
Doc.inp
1
0
1
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
0
1
1
0
Có 3 ô vuông
Test 6:
Ngang.inp
Doc.inp
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
Có 15 ô vuông
---- Hết ----