SỞ GIÁO DỤC VÀ ðÀO TẠO
ðỒNG THÁP
_______________________________

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT
CẤP TỈNH NĂM HỌC 2011 - 2012
_____________________________________________

ðề thi chính thức

ðỀ THI MÔN: TIN HỌC
Ngày thi: 09/10/2011
Thời gian làm bài: 180 phút (Không kể thời gian phát ñề)
(ðề thi gồm có: 02 trang)
Tổng quan ñề thi :
Bài Tên tệp chương trình
Bài 1
BL1.PAS
Bài 2
BL2.PAS
Bài 3
BL3.PAS

Tên tệp input
TONG.INP
AVER.INP
HARVEST.INP

Tên tệp output
TONG.OUT
AVER.OUT

HARVEST.OUT

Bài 1: (8 ñiểm) TỔNG CÁC CHỮ SỐ
Cho ba số nguyên dương n , k và p (n ≤ 15; k ≤ 100)
Yêu cầu 1: Hãy cho biết có bao nhiêu số nguyên dương có số các chữ số KHÔNG vượt
quá n và có tổng các chữ số ñúng bằng k.
Yêu cầu 2: Nếu ñem các số tìm ñược trong yêu cầu 1 sắp xếp tăng dần và ñánh số thứ tự
từ 1 ñến hết thì số thứ p là số nào? (giả thiết p không lớn hơn số lượng các số tìm ñược).
Chẳng hạn, với n = 2, k = 8, p = 6 thì các số có không quá 2 chữ số có tổng các chữ số
bằng 8 là: 8, 17, 26, 35, 44, 53, 62, 71, 80 (có 9 số) và số thứ 6 là số 53.
Dữ liệu vào: Cho từ tệp văn bản TONG.INP gồm một dòng chứa ba số n, k, p theo ñúng
thứ tự, giữa các số cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản TONG.OUT gồm hai dòng:
• Dòng 1: Ghi số lượng các số tìm ñược trong yêu cầu 1.
• Dòng 2: Ghi số thứ p tìm ñược trong yêu cầu 2.
Ví dụ:
TONG.INP

TONG.OUT

2 8 6

9
53

Hạn chế kỹ thuật: Thời gian thực hiện chương trình không quá 3 giây. Có 60% test với
kích thước dữ liệu (n) nhỏ.
Bài 2: (7 ñiểm) DÃY CON DÀI NHẤT
Cho dãy số nguyên A có N phần tử a1, a2, …, aN. (N ≤ 100000, |ai| ≤ 10000 với i=1..N).
Yêu cầu: Tìm dãy con các phần tử liên tiếp dài nhất của dãy A sao cho giá trị trung bình

cộng của các phần tử của dãy con ñó lớn hơn hoặc bằng giá trị K cho trước ( |K| ≤ 10000 ).
Dữ liệu vào: Cho từ tệp văn bản AVER.INP gồm
• Dòng ñầu ghi số hai số nguyên N và K.
• Các dòng tiếp theo lần lượt ghi các số nguyên a1, a2, …, aN.
Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách.

1/2


Kết quả: Ghi ra tệp văn bản AVER.OUT gồm một dòng ghi hai số nguyên lần lượt là ñộ
dài dài nhất của dãy con tìm ñược và vị trí bắt ñầu của dãy con ñó trong dãy A. Giữa hai số ghi
cách nhau ít nhất một dấu cách. Trường hợp không tìm ñược dãy con thỏa ñiều kiện thì ghi số 0.
Ví dụ:
AVER.INP
73
1523141

AVER.OUT
5 2

Hạn chế kỹ thuật: Thời gian thực hiện chương trình không quá 3 giây. Có 60% test với
kích thước dữ liệu (n) nhỏ.
Bài 3: (5 ñiểm) THU HOẠCH
Quýt là một loại trái cây rất ñược thị trường ưa chuộng. Trong một trang trại quýt ñược
trồng thành một hàng gồm n cây. Như vậy với mỗi cây quýt có ñúng hai cây bên cạnh nó ở hai
bên (trừ cây ở ñầu và cuối hàng). Mỗi cây quýt cho năng suất khác nhau. Năm nay, cây thứ i có ai
quả.
Các kỹ sư nông nghiệp ñang thử nghiệm một máy thu hoạch trái cây tự ñộng. Khi ñứng
trước một cây nào ñó, các cánh tay thu lượm có thể hái quả của cây ñó ñồng thời có thể vươn tới
hai cây hai bên ñể hái quả. ðây là thiết bị thử nghiệm nên nguồn pin chỉ ñủ cho 3 lần thao tác tại

3 cây (và các cây bên cạnh 3 cây ñó), sau ñó máy phải quay về giao sản phẩm và nạp lại nguồn.
Yêu cầu: Cho n và các giá trị nguyên ai ( 1 ≤ ai ≤ 1000, 10 ≤ n ≤ 106, i = 1..n). Hãy xác
ñịnh số quả tối ña máy có thể hái ñược trong lần thử nghiệm ñầu tiên.
Dữ liệu vào: Cho từ tệp văn bản HARVEST.INP gồm:
• Dòng ñầu ghi số nguyên n.
• Các dòng tiếp theo lần lượt ghi các số nguyên a1, a2, ...,an. Các số trên cùng một dòng
ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản HARVEST.OUT gồm một số nguyên là số quả nhiều nhất thu
hoạch ñược.
Ví dụ:
HARVEST.INP

HARVEST.OUT

12
2 3 7 1 2 4 5 3 1 8 1 4

37

Hạn chế kỹ thuật: Thời gian thực hiện chương trình không quá 3 giây. Có 60% test với
kích thước dữ liệu (n) nhỏ.HẾT

Họ và tên thí sinh: ________________________

Số báo danh: ___________________________

Chữ ký GT1:_____________________________

Chữ ký GT2:____________________________


2/2