Đề Thi Chọn Đội Tuyển Học Sinh Giỏi Dự Thi Quốc Gia Tỉnh Đắk Lắk Tin Học

SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH ĐẮK LẮK
ĐỀ CHÍNH THỨC
KỲ THI CHỌN ĐỘI TUYỂN HỌC SINH GIỎI DỰ THI QUỐC GIA - Năm học 2010 - 2011
Môn: TIN HỌC 
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
Ngày thi: 30/11/2010
(Đề thi gồm 02 trang)
Bài
File bài làm
Dữ liệu vào
Kết quả
Bài 1: Số hình chữ nhật trên lưới
Bai1.pas
 HCN.INP
 HCN.OUT
Bài 2: Di chuyển từ trái sang phải
Bai2.pas
 Dichuyen.inp
 Dichuyen.out
Bài 1(10,0 điểm) - Số hình chữ nhật trên lưới.
 Trên một tờ giấy kẻ ô vuông, kích thước N x N người ta tạo ra một số hình chữ nhật bằng cách định vị một số ô liên tiếp kề nhau, các hình chữ nhật này từng đôi một không giao nhau, không liền kề theo phép kề đỉnh. Cho bảng A (N x N), giá trị phần tử của bảng được xác định như sau:
 A[i,j] = 1 nếu ô tương ứng trên tờ giấy thuộc một hình chữ nhật nào đấy.
 A[i,j] = 0 nếu ô tương ứng trên tờ giấy không thuộc một hình chữ nhật nào cả.
 Hãy tìm số lượng các hình chữ nhật và các tọa độ đỉnh trái trên, phải dưới của mỗi hình chữ nhật trong bảng.
 Dữ liệu vào lấy từ file văn bản “HCN.INP” dòng đầu ghi số N. N dòng tiếp theo mỗi dòng là xâu nhị phân độ dài N, giá trị 1 nếu ô tương ứng thuộc một hình chữ nhật, giá trị 0 nếu ô tương ứng không thuộc một hình chữ nhật nào cả.
 Kết quả ghi ra file văn bản “HCN.OUT” theo cấu trúc:
Dòng đầu ghi số M là số hình chữ nhật có trong bảng.
M dòng tiếp theo mỗi dòng ghi 4 số p, q, r, s với ý nghĩa: cặp số p, q là tọa độ đỉnh trái trên, cặp số r, s là tọa độ đỉnh phải dưới của một hình chữ nhật trong M hình chữ nhật có trên bảng.
Ví dụ:
HCN.INP
7
1110011
1110011
0111000
0111011
0000011
1111011
1111000
HCN.OUT
5
1 1 2 3
1 6 2 7
3 2 4 4
4 6 6 7
6 1 7 4
Bài 2(10,0 điểm) - Di chuyển từ trái sang phải.
 Cho hình chữ nhật M x N ô vuông, mỗi ô chứa một số nguyên. Có thể di chuyển từ một ô sang ô thuộc cột bên phải cùng dòng hoặc chênh lệch một dòng. Tìm cách di chuyển từ một ô nào đó thuộc cột 1 đến một ô nào đó thuộc cột N sao cho tổng các số nguyên chứa trong các ô đi qua là nhỏ nhất.
 Dữ liệu vào lấy từ file văn bản “Dichuyen.inp” dòng đầu là 2 số nguyên dương M, N. M dòng tiếp theo mỗi dòng ghi N số nguyên của hình chữ nhật.
 Kết quả ghi ra file văn bản “Dichuyen.out” gồm 2 dòng:
Dòng thứ nhất ghi tổng các số nguyên chứa trong các ô đi qua.
Dòng thứ hai ghi N số là chỉ số dòng của các ô đi qua từ cột 1 đến cột N.
Ví dụ:
DICHUYEN.INP
2 3
5 2 3
4 3 2
DICHUYEN.OUT
8
2 1 2 
------------------ 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 CHỌN ĐỘI TUYỂN HỌC SINH GIỎI TỈNH 
 NĂM HỌC 2010-201
 ĐẮK LẮK	 MÔN : TIN HỌC 12 - THPT	
ĐÁP ÁN VÀ HƯỚNG DẪN CHẤM 
I. Phần chương trình nguồn
Bài 1:
Var f:text;
 a: array[1..100,1..100] of 0..1;
 td: array[1..4,1..100] of byte;
 n, dem: byte;
procedure docfile;
var i, j : byte; ch: char;
begin
 fillchar(a,sizeof(a),0);
 dem:=0;
 assign(f,'hcn.inp'); reset(f);
 readln(f,n);
 for i:=1 to n do
 begin
 for j:=1 to n do
 begin
 read(f,ch);
 if ch= '1' then a[i,j]:= 1;
 end;
 readln(f);
 end;
 close(f);
end;
procedure tim;
var
 i,j,k,l,d,c:byte;
begin
 for i:=1 to n do
 for j:=1 to n do
 if a[i,j]=1 then
 begin
 inc(dem);
 td[1,dem]:=i;
 td[2,dem]:=j;
 d:=i; c:=j;
 while (d<n) and (a[d+1,j]=1) do inc(d);
 while (c<n) and (a[i,c+1]=1) do inc(c);
 td[3,dem]:=d; td[4,dem]:=c;
 for k:=i to d do
 for l:=j to c do a[k,l]:=0;
 end;
end;
procedure vietfile;
var i:byte;
begin
 assign(f,'hcn.out');
 rewrite(f);
 writeln(f,dem);
 for i:=1 to dem do
 writeln(f,td[1,i],' ',td[2,i],' ',td[3,i],' ',td[4,i]);
 close(f);
end;
BEGIN
 docfile;
 tim;
 vietfile;
END.
Bài 2:
uses crt;
const maxmn = 100;
 fi = 'bt.inp';
 fo = 'bt.out';
var a,t :array[0..maxmn,0..maxmn] of integer;
 kq :array[1..maxmn] of byte;
 m,n :byte;
procedure doc_file;
 var f :text;
 i,j:byte;
 begin
 assign(f,fi); reset(f); readln(f,m,n);
 for i:=1 to m do
 begin
 for j:=1 to n do read(f,a[i,j]);
 readln(f);
 end;
 close(f);
 end;
function min(i,j:byte):byte;
 var p: integer; d: byte;
 begin
 p:=a[i-1,j-1];
 d:=i-1;
 if a[i,j-1]< p then
 begin
 p:=a[i,j-1];
 d:=i;
 end;
 if a[i+1,j-1]< p then
 begin
 p:=a[i+1,j-1];
 d:=i+1;
 end;
 min:=d;
 end;
procedure tao_nhan;
 var i,j,d : byte;
 begin
 for j:= 0 to n do a[0,j]:= maxint;
 for j:= 0 to n do a[m+1,j]:=maxint;
 fillchar(t,sizeof(t),0);
 for j:=2 to n do
 for i:=1 to m do
 begin
 d := min(i,j);
 a[i,j]:= a[d,j-1]+a[i,j];
 t[i,j]:=d;
 end;
 end;
procedure tim_duong;
 var i,j,d:byte;
 p :integer;
 f :text;
 begin
 p:=maxint;
 for i:=1 to m do
 if a[i,n]< p then
 begin
 d:=i;
 p:=a[1,n];
 end;
 j:=n;
 i:=d;
 kq[j]:=d;
 assign(f,fo); rewrite(f); writeln(f,a[i,j]);
 while j>0 do
 begin
 i:=t[i,j];
 j:=j-1;
 kq[j]:=i;
 end;
 for j:=1 to n do write(f,kq[j],' ');
 close(f);
 end;
 BEGIN
 doc_file;
 tao_nhan;
 tim_duong;
 END.
II. Test chấm
Bài 1:
Test 1
HCN.INP
7
1110011
1110011
0111000
0111011
0000011
1111011
1111000
Test 2
5
11100
11100
01110
01110
00000
HCN.OUT
5
1 1 2 3
1 6 2 7
3 2 4 4
4 6 6 7
6 1 7 4
2
1 1 2 3
3 2 4 4
Bài 2:
Test 1:
DICHUYEN.INP
2 3
5 2 3
4 3 2
Test 2:
3 4
5 2 3 1
4 3 2 0
1 3 6 8
Test 3:
4 5
5 2 3 1 -3 
4 3 2 0 1 
1 3 6 8 -2 
1 2 3 4 5
Test 4:
5 6
 5 2 3 4 -3 1 
 4 3 2 9 1 0
-6 3 8 9 1 2
 0 2 9 0 5 7
 1 2 8 5 0 2
DICHUYEN.OUT
8
2 1 2 
6
3 2 2 2 
3
3 2 2 2 1 
0
3 2 2 1 1 2 
---- Hết ----