SỞ GIÁO DỤC VÀ ĐÀO TẠO
THANH HOÁ

KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HSGQG LỚP 12 THPT
NĂM HỌC 2013 – 2014

ĐỀ CHÍNH THỨC
SBD: ………………

MÔN THI: TIN HỌC
Ngày thi: 08 – 10 – 2013
Thời gian 180 phút, không kể thời gian giao đề
(Đề gồm 3 câu, 2 trang)

Tổng quan bài thi:
Câu

Tên bài

Tên file nguồn

Tên file input

Tên file output

Điểm

1

CHU KỲ


7

Hãy lập trình giải các bài toán sau:
Câu 1. CHU KỲ
Cho xâu S chỉ gồm các kí tự từ '0' đến '9' và từ 'a' đến 'z'. Xâu S bao giờ cũng biểu
diễn được dưới dạng WT.
Ví dụ: ababab = ab3 hoặc ababab1
Yêu cầu: Tìm cách biểu diễn xâu S dưới dạng WT sao cho độ dài của xâu W nhỏ nhất.
Dữ liệu: Vào từ file văn bản CHUKY.INP gồm một dòng chứa xâu kí tự S có độ dài không
vượt quá 107.
Kết quả: Ghi ra file văn bản CHUKY.OUT một số duy nhất là độ dài xâu W tìm được.
Ví dụ:
CHUKY.INP
CHUKY.OUT
ababab
2
Câu 2. CHI PHÍ
Cơ sở mới của trường đã
được xây dựng xong, tuy vậy vẫn
còn một số hạng mục chưa hoàn
thành, trong đó có khu giáo dục
thể chất ngoài trời. Nhà trường
cần hoàn thiện gấp đường chạy
cho các tiết thể dục vào đầu năm
học. Khu giáo dục thể chất ngoài
trời có dạng lưới ô vuông kích
thước n×m ô. Các hàng và cột đánh số từ 1, từ trên xuống dưới và từ trái qua phải. Ô xuất
phát và ô kết thúc đường chạy là cố định và được cho trước. Cần phải tổ chức dọn dẹp, san
lấp các ô để được một đường chạy độ rộng một ô và bao gồm các ô kề cạnh. Chi phí dọn
dẹp các ô có thể là khác nhau, vì vậy cần chọn đường chạy sao cho tổng chi phí dọn dẹp là

cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch
giữa tọa độ X không quá 1 và chênh lệch tọa độ Y không quá 1.
Yêu cầu: Hãy giúp John xác định số lượng đỉnh đồi trên bản đồ.
Dữ liệu: Vào từ file văn bản CANHGAC.INP gồm:
- Dòng đầu chứa hai số nguyên N và M được cách nhau bởi dấu cách (1
end;
{=============================}
begin
docdl;
assign(f,fo); rewrite(f);
n:=length(s);
i:=1;
while (i
if (p=0) or (d[vt[p].u,vt[p].v]
begin
d[ux,vy]:=d[u,v]+c[ux,vy];
capnhat(ux,vy);
end;
end;
until false;
end;
procedure
xuli;
begin
dijktra;
end;
BEGIN
docfile;
xuli;
dongfile;
END.

Trang 5/ 10


CONST
tfi='canhgac.INP';
tfo='canhgac.OUT';
dh:array[1..8]of longint=(0,-1,0,1,-1,-1,1,1);
dc:array[1..8]of longint=(1,0,-1,0,1,-1,-1,1);
max=701;
VAR
fi,fo:text;
LT,dd,a:array[0..max,0..max]of longint;

Var i,j:longint;
Begin
assign(fi,tfi); reset(fi);
read(fi,m,n);
for i:=1 to m do
for j:=1 to n do read(fi,a[i,j]);
close(fi);
End;
Procedure Init;
Var i,j,ii,jj,k:longint;
Begin
//dd[i,j]=0 <---> i,j nam tren dinh doi
//dd[i,j]=1 <---> i,j khong nam tren dinh doi
Fillchar(dd,sizeof(dd),0);
for i:=1 to m do

Trang 6/ 10


for j:=1 to n do
begin
for k:=1 to 8 do
begin
ii:=i+dh[k]; jj:=j+dc[k];
if (ii>=1) and (ii<=m) and (jj>=1) and (jja[i,j] then dd[i,j]:=1;
if a[ii,jj]
if (dd[i,j]=0) and (LT[i,j]=0) then
begin
inc(res);
LT[i,j]:=res;
BFS(doiso(i,j));
end;
End;
Procedure Process;
Begin
Init;
Calculate;
End;
Procedure Output;
Var i,j:longint;
Begin
assign(fo,tfo); rewrite(fo);

Trang 7/ 10


writeln(fo,res);
close(fo);
End;
BEGIN
Input;
Process;
Output;
END.

Trang 8/ 10