HSG lớp 9 Hà Nội 2016-2017

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI ĐỀ CHÍNH THỨC

KÌ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Năm học 2016 - 2017
Môn thi: Tin học - Ngày thi: 28/3/2017
Thời gian làm bài: 150 phút
(Đề thi gồm 02 trang)

---

Câu 1. Đếm số (6 điểm)

Tên tệp chương trình: CAU1.*

Cho hai số nguyên dương n và k, với 1 ≤ k < n.

Yêu cầu: Đếm xem trong các số nguyên từ 1 đến n có bao nhiêu số có đúng k ước số nguyên dương khác nhau.

Dữ liệu: Vào từ tệp văn bản CAU1.INP: hai số nguyên dương n và k (1 ≤ k < n ≤ 10⁵).

Kết quả: Ghi ra tệp văn bản CAU1.OUT: số lượng các số có đúng k ước số nguyên dương khác nhau.

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
8 4	2	Trong các số từ 1 đến 8, hai số 6, 8 có 4 ước nguyên dương khác nhau: số 6 có 4 ước là 1, 2, 3, 6; số 8 có 4 ước là 1, 2, 4, 8.

Câu 2. Siêu thị (5 điểm)

Tên tệp chương trình: CAU2.*

Một siêu thị thực hiện chương trình ưu đãi cho khách hàng như sau: khi khách hàng mua với số lượng p sản phẩm, nếu p ≥ k thì không phải thanh toán tiền cho một sản phẩm có giá tiền nhỏ nhất. Ví dụ: với k = 2, khi mua 3 sản phẩm có giá lần lượt là 250, 1000, 200, khách hàng không phải thanh toán tiền cho sản phẩm có giá 200 và chỉ phải trả tổng số tiền là 1250.

Một khách hàng cần mua n sản phẩm ở siêu thị và biết sản phẩm thứ i (1 ≤ i ≤ n) có giá tiền là aᵢ. Khách hàng có thể thực hiện mua n sản phẩm thành nhiều lần để được hưởng ưu đãi của siêu thị một cách có lợi nhất.

Yêu cầu: Tìm tổng số tiền ít nhất mà khách hàng phải trả khi mua đủ n sản phẩm.

Dữ liệu: Vào từ tệp văn bản CAU2.INP:

• Dòng đầu chứa hai số nguyên n và k (1 ≤ n ≤ 10³, 2 ≤ k ≤ 10²);
• Dòng sau chứa n số nguyên dương aᵢ (1 ≤ i ≤ n), mỗi số không vượt quá 10⁶.

Kết quả: Ghi ra tệp văn bản CAU2.OUT: tổng số tiền ít nhất mà khách hàng phải trả.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
5 2 250 1000 100 3000 200	3350	Khách hàng sẽ mua 5 sản phẩm thành 3 lần: - Lần 1 mua 2 sản phẩm 2, 4: số tiền phải trả là 3000; - Lần 2 mua 2 sản phẩm 1, 5: số tiền phải trả là 250; - Lần 3 mua 1 sản phẩm 3: số tiền phải trả là 100. Tổng số tiền ít nhất phải trả là 3350.

Câu 3. Biến đổi xâu kí tự (5 điểm)

Tên tệp chương trình: CAU3.*

Cho n xâu kí tự s₁, s₂, …, sₙ và một xâu mẫu s có cùng độ dài d chỉ gồm các chữ cái thường tiếng Anh. Một phép biến đổi xâu (i, j, k) thực hiện đổi chỗ kí tự thứ k của hai xâu sᵢ và sⱼ (1 ≤ i < j ≤ n, 1 ≤ k ≤ d).

Yêu cầu: Tìm số lượng ít nhất các phép biến đổi xâu cần thực hiện trên n xâu s₁, s₂, …, sₙ để nhận được xâu mẫu s.

Dữ liệu: Vào từ tệp văn bản CAU3.INP:

• Dòng đầu chứa số nguyên n (2 ≤ n ≤ 100);
• Trong n dòng tiếp theo, dòng thứ i (1 ≤ i ≤ n) chứa xâu sᵢ gồm d chữ cái thường tiếng Anh (2 ≤ d ≤ 100);
• Dòng cuối chứa xâu mẫu s gồm d chữ cái thường tiếng Anh.

Kết quả: Ghi ra tệp văn bản CAU3.OUT: số lượng ít nhất các phép biến đổi xâu cần thực hiện. Trong trường hợp không có phương án tiến hành các phép biến đổi xâu trên n xâu s₁, s₂, …, sₙ để nhận được xâu mẫu s thì ghi số -1.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
3 abc cab bca acb	2	- Thực hiện phép biến đổi xâu (1, 3, 2): đổi chỗ kí tự thứ 2 của xâu 1 và 3 nhận được xâu s₁ = ‘acc’, s₃ = ‘bba’; - Thực hiện phép biến đổi xâu (1, 2, 3): đổi chỗ kí tự thứ 3 của xâu 1 và 2 nhận được xâu s₁ = ‘acb’ chính là xâu mẫu s đã cho.

Câu 4. Xây dựng đường băng (4 điểm)

Tên tệp chương trình: CAU4.*

Thành phố Anpha dự định xây dựng sân bay trên một vùng đất mô tả bởi bản đồ hình chữ nhật được chia thành lưới các ô vuông gồm m hàng, n cột. Mỗi ô trên bản đồ chứa một số nguyên (đơn vị mét) là độ cao (so với mực nước biển) của một ô đất ngoài thực địa. Thành phố dự định thiết kế một đường băng cho sân bay nằm trọn vẹn trong bản đồ này. Để làm đường băng cần phải san phẳng một dãy các ô liền nhau tạo thành hình chữ nhật có chiều dài ≥ d ô, chiều rộng ≥ r ô và độ cao của mỗi ô là h mét. Chi phí để san phẳng các ô trên đường băng này bằng tổng độ chênh lệch giữa độ cao mỗi ô đã chọn so với h.

Yêu cầu: Xác định chi phí nhỏ nhất để san phẳng các ô được chọn xây dựng đường băng.

Dữ liệu: Vào từ tệp văn bản CAU4.INP:

• Dòng đầu chứa hai số nguyên m, n (2 < m, n ≤ 500);
• Dòng thứ hai chứa ba số nguyên d, r, h (1 ≤ r < d ≤ 300, 1 < h ≤ 10⁴);
• Trong m dòng tiếp theo, dòng thứ i chứa n số nguyên mô tả độ cao các ô trong hàng thứ i của bản đồ, mỗi số có giá trị tuyệt đối không vượt quá 10⁴.

Kết quả: Ghi ra tệp văn bản CAU4.OUT: chi phí nhỏ nhất để san phẳng các ô đã chọn. Trong trường hợp không có phương án xây dựng đường băng thì ghi số -1.

Ví dụ:

CAU4.INP	CAU4.OUT
5 6 4 2 2 3 4 2 4 3 3 4 5 2 2 5 3 1 4 3 2 5 4 3 4 2 1 5 3 3 4 2 3 1 5	3

Giải thích: Tọa độ các ô cần san phẳng để xây dựng đường băng có chi phí nhỏ nhất gồm: (2, 3), (2, 4), (3, 3), (3, 4), (4, 3), (4, 4), (5, 3), (5, 4) - các số in đậm dưới đây:

3 4 2 4 3 3
4 5 2 2 5 3
1 4 3 2 5 4
3 4 2 1 5 3
3 4 2 3 1 5

---

Chú ý:

• Cán bộ coi thi không giải thích gì thêm;
• Các tệp dữ liệu vào là đúng đắn không cần kiểm tra;
• Làm bài với các tên tệp đúng như quy định trong đề, trong đó dấu * là phần mở rộng mặc định theo ngôn ngữ lập trình mà thí sinh sử dụng (ví dụ: CAU1.PAS, CAU1.CPP, …).