Bài soạn Đề_ĐA_HSG Tỉnh ĐăkLăk_V2_2010
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (155.32 KB, 7 trang )
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
Trang 1
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………….....
Trang 2
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;
Trang 3
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
Trang 4
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];
Trang 5
