HomeHọc sinh giỏi môn tin

Đề thi HSG tin 9 TP Hồ Chi Minh – Năm học 2016 – 2017

Like Tweet Pin it Share Share Email
Like và share giúp mình phát triển website nhé.
  •  
  •  

Đề thi HSG tin 9 TP Hồ Chi Minh – Năm học 2016 – 2017

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 ≤ 109).

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 ≤ 109).

 

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 Hij 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 Hij theo thứ tự của ma trận (0

≤ Hij ≤ 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 3
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

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

Comments (10)

Trả lời

Your email address will not be published. Required fields are marked *