THÀNH PHỐ HỒ CHÍ MINH
KỲ THI HỌC SINH GIỎI LỚP 9 THCS
KHÓA NGÀY 29/3/2018
Môn thi: Tin học
ĐỀ THI CHÍNH THỨC
(Đề thi có 02 trang)
Thời gian làm bài: 150 phút
(Không kể thời gian phát đề)
TỔNG QUAN BÀI THI
Tên bài Tên chương trình Tập tin dữ liệu Tập tin kết quả
Bài 1 Số lượng số Fibonaci CFIBO.* CFIBO.INP CFIBO.OUT
Bài 2 Tưới ruộng FARM.* FARM.INP FARM.OUT
Bài 3 Vay và trả ZDIST.* ZDIST.INP ZDIST.OUT
Dấu * được thay thế bởi PAS hay CPP của ngôn ngữ lập trình được sử dụng tương ứng
là Pascal hoặc C++.
Hãy lập trình giải 3 bài toán sau:
Bài 1: Số lượng số Fibonaci – CFIBO.* (6 điểm)
"Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con
(cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ
ra một đôi thỏ con, và quá trình sinh cứ thế tiếp diễn. Hỏi n tháng có bao nhiêu đôi thỏ, nếu
đầu năm có một đôi thỏ sơ sinh? Đó là câu chuyện vui về số Fibonaci, số này được định nghĩa
như sau:
- f(0) = 0.
- f(2) = f(1) = 1.
- f(n)= f(n-1) +f(n-2) với n > 2.
Yêu cầu: Cho hai số nguyên dương A và B, Tính số lượng số Fibonaci có giá trị trong
đoạn [A..B].
Dữ liệu vào: từ tập tin văn bản CFIBO.INP gồm hai số nguyên dương A và B cách
nhau ít nhất một khoảng trắng (0 ≤ A ≤ B ≤ 2*10
10
).
Kết quả: ghi ra tập tin văn bản CFIBO.OUT một số nguyên duy nhất là số lượng số
Fibonaci có giá trị trong đoạn [A..B].
CFIBO.INP CFIBO.OUT
2 10 4
Giải thích: Các 4 số Fibonaci f(3)=2, f(4)=3, f(5)=5 và f(6)=8 thỏa.
Bài 2: Tưới ruộng – FARM.* (7 điểm)
Trên khu đất ruộng hình chữ nhật, được chia thành từng thửa vuông đều nhau có cạnh
là một đơn vị để cho các tá điền thuê lại trồng trọt. Tại một số thửa ruộng, bạn Bờm cho đào
giếng để lấy nước tưới. Vì năm nay trời hạn nên mỗi giếng chỉ đủ nước để tưới cho các thửa
ruộng xung quanh trong phạm vi bán kính 2 ô vuông đơn vị. Các tá điền không thể đưa nước
đi xa vì họ không có dụng cụ cũng không đủ sức đưa đi.
Yêu cầu: Hãy đếm xem có bao nhiêu thửa ruộng sẽ không tưới được.
Ví dụ: Với diện tích ruộng 6*9 như hình bên có 3 giếng nước
tại các ô ở dòng 2 cột 6, dòng 3 cột 2 và dòng 5 cột 7. Các ô tô đen
chính là những ô không thể tưới.
Dữ liệu vào: Trong tập tin văn bản FARM.INP gồm:
- Dòng đầu là hai số nguyên dương M và N cách nhau một
dấu cách cho biết kích thước khu đất (1< M, N ≤ 100);
- Dòng thứ hai là một số nguyên dương K cho biết số giếng đã đào trên khu đất;
Đề thi Học sinh giỏi Lớp 9 – môn Tin học Trang 1/2
- Trên K dòng tiếp theo, mỗi dòng ghi hai số nguyên dương tương ứng với chỉ số dòng
và cột của từng giếng đào trên khu đất, các số cách nhau một dấu cách. Chỉ số dòng được
đánh số từ 1, tính từ trên xuống dưới của bảng. Chỉ số cột được đánh số từ 1, tính từ trái sang
phải của bảng (0 ≤ K ≤ 10
4
).
Kết quả: Ghi vào tập tin văn bản FARM.OUT gồm một số nguyên duy nhất là số
thửa ruộng không thể tưới.
Ví dụ:
FARM.INP FARM.OUT
6 9
3
2 6
3 2
5 7
6
Bài 3: Vay và trả - ZDIST.* (7 điểm)
“Hãy khôn ngoan trong kinh doanh” Hãy xem Bờm đã vận dụng thế nào? Cậu ấy đã
nợ hoặc tạm ứng cho các khách hàng, có N khách để thuận tiện đánh số từ 1 đến N.
Ngày kết thúc cuối cùng đã đến. Cậu ấy biết không thể trả khi không có đủ tiền. Có tất
cả N khách hàng xếp theo một đường thẳng với khoảng cách đều nhau 1 đơn vị. Bờm sẽ thu
tiền người nợ và sẽ trả cho khách mình đang nợ khi số tiền đủ trả, không nhất thiết nhận hết
rồi mới trả nhưng luôn về đích khi kết thúc.
Khi cậu di chuyển tới, người nợ sẽ trả, và khi có đủ cậu sẽ trả cho các người mình nợ.
Người i nợ Bờm D
i
tiền. Dấu trừ (-) có nghĩa là Bờm nợ tiền.
Bờm bắt đầu ở vị trí 0 và phải kết thúc chuyến đi của mình ở vị trí người cuối cùng.
Hãy tính quãng đường ngắn nhất mà cậu ấy phải đi để thu tiền nợ và trả tất cả những người
cậu ấy nợ? Trường hợp không đủ tiền trả thì Bờm sẽ quay vị trí cuối và vẫn còn nợ.
Dữ liệu vào: Trong tập tin văn bản ZDIST.INP có cấu trúc:
- Dòng 1 là một số nguyên N (1≤ n ≤ 10
);
- n dòng kế tiếp mỗi dòng chứa số nguyên D
i
5
(-10
3
≤ D
i
≤ 10
3
)
Kết quả: Ghi ra tập tin văn bản ZDIST.OUT có một số nguyên duy nhất là quãng
đường tối thiểu phải đi theo yêu cầu.
Ví dụ:
ZDIST.INP ZDIST.OUT ZDIST.INP ZDIST.OUT
5
100
-200
250
-200
150
9 5
Giải thích ví dụ 1 (bên trái):
Bắt đầu 100 -200 250 -200 150
100
-200
250
-200
10
- Đi 1 đơn vị nhận được 100 (số bước: 1)
- Đi tiếp 2 đơn vị nhận được 350 (số bước: 3)
- Quay lại 1 đơn vị trả 200 còn 150 (số bước: 4)
- Đi tiếp 3 đơn vị để nhận 150 (số bước: 7)
- Quay lại 1 đơn vị và trả 200 (số bước: 8)
- Đi tiếp 1 đơn vị để về vị trí kết thúc (số bước: 9)
------ Hết ------
7
Đề thi Học sinh giỏi Lớp 9 – môn Tin học Trang 2/2
Không có nhận xét nào:
Đăng nhận xét
Lưu ý: Chỉ thành viên của blog này mới được đăng nhận xét.