Đề thi HSGTHCS Lâm Đồng

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 ( 0M; 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:
F1=1; F2=1; Fi=Fi-1+Fi-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 (N2000000000)
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 (0N10000), phần thưởng thứ I có giáo trị là ai (1ai100). 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