Đề thi HSGTHCS Lâm Đồng
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 (57.77 KB, 6 trang )
SỞ GIÁO DỤC & ĐÀO TẠO KÌ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
LÂM ĐỒNG NĂM HỌC 2010-2011
ĐỀ CHÍH THỨC Môn TIN HỌC – THCS
(Đề thi có 02 trang: gồm 3 bài) Thời gian: 150 phút (Không kể thời gian giao đề)
Cấu trúc đề thi:
stt Tên bài Tên file làm bài Tên file INPUT Tên file OUTPUT
1 PHÂN TỬ YÊN
NGỰA
PTYN.PAS PTYN.INP PTYN.OUT
2 TỔNG CÁC SỐ
FIBONACI
FIBO.PAS FIBO.INP FIBO.OUT
3 CHỌN PHẦN
THƯỞNG
PTHUONG.PAS PTHUONG.INP PTHUONG.UOT
Bài 1: (6điểm). PHẦN TỬ YÊN NGỰA
Cho mảng hai chiều có kích thước MxN số nguyên. Phần tử A[I,j] được gọi là phần tử yên
ngựa nếu nó là phần tử nhỏ nhất trong hàng I đồng thời là phần tử lớn nhất trong cột j.
Em hãy lập chương trình tìm phân tử yên ngựa của mảng A.
Dữ liệu vào: Cho file PTYN.INP gồm
- Dòng đầu tiên gồm hai số M,N ( 0
≤
M; N
≤
100)
- M dòng tiếp theo, mỗi dòng gồm có N số nguyên của mảng A.
(các giá trò cách nhau ít nhất 1 khoảng cách).
Dữ liệu ra: Ghi file PTYN.OUT vò trí của các phân tử yên ngựa (nếu có) hoặc dòng thông
báo “Không có phần tử yên ngựa”.
Ví dụ:
PTYN.INP PTYN.OUT
3 3
15 3 9
55 4 6
76 1 2
(2,2)
Hoặc
PTYN.INP PTYN.OUT
3 3
15 10 5
55 4 6
76 1 2
Khong co phantu yen ngua
Bài 2: (7 điểm). TỔNG CÁC SỐ FIBONACI
Dãy Fibonaci là dãy gồm các số: 1; 1; 2; 3; 5; 8; … được xác đònh bởi công thức sau:
F
1
=1; F
2
=1; F
i
=F
i-1
+F
i-2
với i>2
Em hãy biểu diễn một số tự nhiên tành tổng ít nhất các số Fibonaci khác nhau.
Dữ liệu vào: Cho file FIBO.INP chứa số N (N
≤
2000000000)
Dữ liệu ra: ghi vào file FIBO.OUT biễu diễn số N thành tổng ít nhất các số Fibonaci khác
nhau.
Ví dụ.
FIBO.INP FIBO.OUT
129 129=89+34+5+1
Hoặc
FIBO.INP FIBO.OUT
8 8=8
Bài 3. (7 điểm) CHỌN PHẦNTHƯỞNG
Trong kỳ thi học sinh giỏi môn tin học, em là người đạt giải đặc biệt. Ban tổ chức cho pép
em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy dược đánh dấu từ
số 1 đấn số N (0
≤
N
≤
10000), phần thưởng thứ I có giáo trò là ai (1
≤
ai
≤
100). Em được phép
chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần thưởng liên tiếp nhau
trong dãy.
Viết chương trình để máy tính hướng dẫn em chọn các phần thưởng sao cho tổng giá trò các
phần thưởng nhận được là lớn nhất.
Dữ liệu vào: cho file PTHUONG.INP gồm các dòng:
- Dòng đầu tiên là số phần thưởng N
- N dòng tiếp theo là giá trò của các phần thương.
Dữ liệu ra: ghi vào file PTHUONG.OUT gồm các dòng:
- Dòng đầu tiên ghi tổng giá trò lớn nhất của phần thưởng đã chọn.
- Dòng tiếp theo ghi vò trí của các phần thưởng đã chọn theo thứ tự tăng dần.
Ví dụ:
PTHUONG.INP PTHUONG.OUT
5
6
9
1
3
5
23
1 2 4 5
Hoặc
PTHUONG.INP PTHUONG.OUT
7
6
9
1
3
5
10
4
32
1 2 4 6 7
Họ và tên thí sinh: Số báo danh
Giám thò 1: Ký tên
Giám thò 2: Ký tên
Bài giải.
Bài 1: (6điểm). PHẦN TỬ YÊN NGỰA
program yenngua;
uses crt;
type
mang=array[1 100,1 100] of integer;
var
a:mang;
n,i,j,d:integer;
f:text;
procedure nhap;
var
i,j:integer;
begin
assign(f,'PTYN.inp');
reset(f);
readln(f,n);
for i:=1 to n do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
end;
function maxc(h:integer):integer;
var
max, i:integer;
begin
max:=a[1,h];
for i:=1 to n do if max<a[i,h] then max:=a[i,h];
maxc:=max;
end;
function minh(h:integer):integer;
var
min, i:integer;
begin
min:=a[h,1];
for i:=1 to n do if min>a[h,i] then min:=a[h,i];
minh:=min;
end;
begin
clrscr;
nhap;
d:=0;
for i:=1 to n do
for j:=1 to n do
if ((a[i,j]=minh(i)) and (a[i,j]=maxc(j))) then d:=d+1;
assign(f,'PTYN.out');
rewrite(f);
for i:=1 to n do
for j:=1 to n do
if ((a[i,j]=minh(i)) and (a[i,j]=maxc(j))) then writeln(f,'(',i, ',',j,')');
if d=0 then write(f,'Khong co phan tu yen ngua');
close(f);
end.
Bài 2: (7 điểm). TỔNG CÁC SỐ FIBONACI
Program TongFIBONACi;
uses crt;
var
i,j,n,m:longint;
f:text;
function fi(h:integer):longint;
var
i:integer;
x,y,tg:longint;
begin
if (h=1) or (h=2) then fi:=1
else
begin
x:=1; y:=1;
for i:=1 to h do
begin
tg:=x;
x:=y;
y:=y+tg;
end;
fi:=y;
end;
end;
function vt(so:longint):integer;
var
i:integer;
begin
i:=1;
while fi(i)< so do i:=i+1;
if fi(i)= so then vt:=i
else vt:=i-1;
end;
procedure doc;
begin
assign(f,'FIBO.INP');
reset(f);
read(f,n);
close(f);
end;
begin
doc;
assign(f,'FIBO.OUT');
rewrite(f);
write(f,n,'=');
write(f,fi(vt(n)));
n:=n-fi(vt(n));
while n<>0 do
begin
m:=fi(vt(n));
n:= n-fi(vt(n));
write(f,'+',m );
end;
close(f);
end.
Baứi 3. (7 ủieồm) CHOẽN PHANTHệễNG
program phan_thuong;
uses crt;
type mang= array[0 10000 ] of byte;
var a,d,m:mang;
dd:array[1 20,1 400] of byte;
b:array [1 10000] of boolean;
r,dem, t,n,max,i,j:integer;
f:text;
procedure doc;
var i:integer;
begin
assign(f,'pthuong.inp');
reset(f);
readln(f,n);
for i:=1 to n do readln(f,d[i]);
close(f);
end;
function kt( c:mang):boolean;
var
i,j:longint;
q:boolean;
begin
i:=1; q:=true;
while (i<=r-2) and q do
begin
j:=1;
while c[i+j-1]+1=c[i+j] do j:=j+1;
if j>=3 then q:=false
else q:=true;
i:=i+1;
end;
kt:=q;
end;
Procedure print;
var i,tong: byte;
begin
if kt(a)=true then
begin
dem:=dem+1;
tong:=0;
for i:=1 to r do
begin
dd[dem,i]:= a[i];
tong:=tong+d[a[i]];
end;
m[dem]:=tong;
end;
end;
Procedure Find(k:byte);
var j: byte;
begin
if k>r then print
else
begin
for j:=1 to n do
if b[j] and (j>a[k-1]) then
begin
a[k]:=j;
b[j]:=false;
Find(k+1);
b[j]:=true;
end;
end;
end;
begin
clrscr;
doc;
dem:=0;
r:= n-(n div 3);
for t:=1 to n do b[t]:=true;
a[0]:=0;
Find(1);
max:=m[1];
for i:=1 to dem do if max< m[i] then max:=m[i];
assign(f,'PTHUONG.OUT');
rewrite(f);
writeln(f,max);
for i:=1 to dem do
if max=m[i] then
begin
j:=1;
while (dd[i,j] <>0) do
begin
write(f,dd[i,j]:2);
j:=j+1;
end;
end;
close(f);
end.
