Đề thi và đáp án HSG tỉnh 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