De thi HSG Tin hoc TP Da Nang 2009

HỘI THI TIN HỌC TRẺ THÀNH PHỐ ĐÀ NẴNG
LẦN THỨ XII ( NĂM 2009
Đề Thi Lập Trình Khối B (Trung học Cơ sở)
(Đề thi gồm có 2 trang)
Thời gian làm bài: 120 phút
(Không tính thời gian giao đề)

ĐỀ CHÍNH THỨC :

Tổng quan
Bài 1
Bài 2
Bài 3
Bài 4

Tên bài làm
BL1.PAS
BL2.PAS
BL3.PAS
BL4.PAS

Dữ liệu vào
Nhập từ bàn phím
Nhập từ bàn phím
RECT.INP
FIBO.INP

Dữ liệu ra
In ra màn hình
In ra màn hình
RECT.OUT
FIBO.OUT

Giới hạn
1 giây
1 giây
2 giây
2 giây


Bài 1:(5 điểm)
Viết chương trình nhập vào từ bàn phím một số N nguyên dương
(1<=N<32767). In ra màn hình các thông tin sau:
a) Số các ước số nguyên dương của số N.
b) Tổng số các ước số nguyên dương của N.
Ví dụ: Nhập từ bàn phím N = 10
In ra màn hình:
Co tat ca 4 uoc so
Tong cac uoc la 18

Bài 2:(5 điểm)
Nhập từ bàn phím một xâu kí tự S và một kí tự K.
Hãy in ra màn hình số lượng kí tự K có trong xâu kí tự S và các vị trí xuất hiện của kí tự K trong xâu S. Nếu không có kí tự K trong xâu S thì in ra màn hình dòng thông báo:
Khong co
Ví dụ:
Xâu kí tự S và kí tự K nhập từ bàn phím
In ra màn hình

KITHITINHOCTRETHANHPHO
T
4
3 6 12 15

SOGIAODUC
M
Khong co


Bài 3: RECTANGLE (7,5 điểm)
Trên giấy kẻ ô khổ N x N có vẽ một số hình chữ nhật. Mỗi hình chữ nhật được tạo ra từ các ô nguyên vẹn, các hình chữ nhật khác nhau không chồng lên nhau và không tiếp xúc nhau (Ví dụ : Hình vẽ dưới đây có 4 hình chữ nhật).

























































Cho mảng A có kích thước N x N, trong đó A[i,j]=1 nếu ô [i,j] thuộc một hình chữ nhật nào đó, còn A[i,j] =0 trong trường hợp ngược lại.
Hãy viết chương trình xác định số các hình chữ nhật có trong bảng.
Dữ liệu vào: Từ File văn bản RECT.INP có cấu trúc như sau:
- Dòng đầu tiên ghi số nguyên dương N (N<=250).
- N dòng tiếp theo mỗi dòng ghi N số 0 hoặc 1 là các phần tử của mảng, mỗi số viết cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra File văn bản RECT.OUT gồm duy nhất một số là số hình chữ nhật tìm được.
Ví dụ:
RECT.INP
RECT.OUT

4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0

7
1 0 0 0 0 0 0
0 0 1 1 1 0 0
1 0 1 1 1 0 0
1 0 1 1 1 0 0
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 1 1
4


Bài 4: FIBONACCI (7,5 điểm)
Dãy số Fibonacci được định nghĩa như sau:
U1 = U2 = 1; Un+1 = Un + Un-1 (với mọi số nguyên dương n, n > 1).
Như vậy, dãy số Fibonacci có dạng sau: 1, 1, 2, 3, 5, 8, 13, 21, 34,…
Với một số tự nhiên x bất kỳ khác 0 ta có thể phân tích thành tổng các số Fibonacci khác nhau (số số hạng của tổng có thể là từ 1 trở lên). Chẳng hạn x = 9, khi đó, ta có:
9 = 1 + 8 hoặc 9 = 1 + 3 + 5
Trong hai cách phân tích trên thì cách thứ hai có số số hạng nhiều nhất (3 số hạng).
Yêu cầu: Cho trước một số nguyên dương x (x <= 10000). Hãy cho biết, nếu biểu diễn x thành tổng của các số Fibonacci khác nhau thì số số hạng nhiều nhất của một tổng là bao nhiêu?
Dữ liệu vào: Cho trong file