---
THÀNH PHỐ HỒ CHÍ MINH
Đề thi chính thức
Đề thi có 2 trang
ĐỀ THI HỌC SINH GIỎI LỚP 9 THCS CẤP THÀNH PHỐ
KHÓA THI NGÀY 20.03.2017
Môn thi: TIN HỌC
Thời gian: 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 Nhân kiểu mới
2MULT.* 2MULT.INP 2MULT.OUT
Bài 2 Mua vé
BTICK.* BTICK.INP BTICK.OUT
Bài 3 Đỉnh đồi
TOP.* TOP.INP TOP.OUT
Dấu * thay thế cho CPP hoặc PAS.
Hãy lập trình giải 3 bài toán sau:
Bài 1: Nhân kiểu mới - 2MULT.* (6 điểm)
Gấu nhà ta rất tức tối trước những phép nhân dài dằng dặc ở trong lớp, cậu ta liền xây
dựng một phép nhân của mình như sau: A*B thay vì nhân bình thường sẽ là tổng các thành
phần của A nhân với các thành phần của B. Ví dụ kết quả của phép nhân của Gấu 123*45 là
1*4 + 1*5 + 2*4 + 2*5 + 3*4 + 3*5 = 54.
Yêu cầu: Cho hai số nguyên A và B cách nhau ít nhất một khoảng trắng, xác định giá trị A*B
theo kiểu nhân của Gấu.
Dữ liệu đọc từ tập tin văn bản 2MULT.INP trong đó chứa số A và B (1 ≤ A, B ≤ 10
).
Kết quả ghi ra tập tin văn bản 2MULT.OUT kết quả tìm được.
Ví dụ:
2MULT.INP 2MULT.OUT
123 45 54
Bài 2: Mua vé - BTICK.* (7 điểm)
“Kẹt xe” do phương tiện cá nhân quá nhiều và ý thức tham gia chưa tốt là một vấn nạn
của các thành phố lớn tại Việt Nam ta. Một trong những giải pháp nhằm giải quyết vấn nạn
này là tăng số lượng phương tiện chuyên chở công cộng để tiến tới hạn chế phương tiện cá
nhân như một số nước trong khu vực đã thực hiện. Để khuyến khích mọi người sử dụng các
phương tiện giao thông công cộng trong thành phố, ngoài việc bán vé rời từng vé một với giá
p1, ta có cách bán cả tập vé mỗi tập k vé với giá p2 cho mỗi tập.
Bờm dự định đến thành phố tham quan và sẽ đi n chuyến trên các phương tiện giao thông
công cộng. Vấn đề đặt ra là nên mua vé như thế nào để tiết kiệm tiền nhất. Dĩ nhiên, Bờm sẽ
không đi lậu vé.
Yêu cầu: Cho 4 số nguyên dương n, k, p1, p2. Nếu k = 1 thì p1 = p2. Hãy tính chi phí tối thiểu
cần thiết để mua vé.
Dữ liệu: Vào từ tập tin văn bản BTICK.INP chứa 4 số nguyên n, k, p1, p2 cách nhau ít nhất
một khoảng trắng (1 ≤ n, k, p1, p2 ≤ 10
9
).
9
Kết quả: Ghi vào tập tin văn bản BTICK.OUT một số nguyên duy nhất là chi phí tối thiểu
Bờm phải bỏ ra.
Ví dụ:
BTICK.INP BTICK.OUT
12 10 17 120 154
Bài 3: Đỉnh đồi - TOP.* (7 điểm)
Đồn điền trà của gia đình Tý nằm trên địa hình có nhiều ngọn đồi, để bảo vệ đồn điền gia
đình giao cho Tý tính toán số người cần thiết để canh gác trên các ngọn đồi này.
Vấn đề là sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác
trên đỉnh của mỗi đồi. Tý có bản đồ của đồn điền là một ma trận gồm N hàng và M cột. Mỗi
phần tử của ma trận có độ cao H
ij
so với mặt nước biển là 0 của ô (i,j). Hãy giúp Tý xác định
số lượng đỉnh đồi trên bản đồ.
Đỉnh đồi là 1 hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi
cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch
giữa tọa độ X không quá 1 và chênh lệch tọa độ Y không quá 1.
Dữ liệu vào: đọc từ tập tin văn bản TOP.INP có cấu trúc:
- Dòng đầu chứa 2 số nguyên N, M cách nhau ít nhất một khoảng trắng (1 < N ≤ 100),
(1 < M ≤ 70);
- N dòng tiếp theo mỗi dòng là M số nguyên mô tả độ cao H
ij
theo thứ tự của ma trận (0
≤ H
ij
≤ 10000).
Kết quả: Xuất ra tập tin văn bản TOP.OUT một số N duy nhất là số đỉnh đồi tìm được.
Ví dụ:
TOP.INP TOP.OUT
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
3
Giải thích:
Có 3 đỉnh đồi, 1 đỉnh đồi có độ cao 4 là ô nằm ở góc trên bên trái, 1 đỉnh đồi là các ô có độ cao
2 ở phía dưới bản đồ và đỉnh đồi còn lại là các ô có độ cao 1 ở góc phải bản đồ (tô xám).
HẾT
GIÁM THỊ KHÔNG ĐƯỢC GIẢI THÍCH GÌ THÊM.
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.