HSG lớp 9 TP. Hồ Chí Minh 2020-2021

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ HỒ CHÍ MINH ĐỀ CHÍNH THỨC
(Đề thi gồm 02 trang)

KỲ THI HỌC SINH GIỎI LỚP 9 THCS Khóa ngày 17.3.2021
Môn thi: Tin học
Thời gian làm bài: 120 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ả
CHE MÁT CHO VƯỜN	CHEVUON.*	CHEVUON.INP	CHEVUON.OUT
ĐẾM TỪ TRÙNG LẮP	DEMTUTL.*	DEMTUTL.INP	DEMTUTL.OUT

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. Các tập tin chương trình lưu trong cùng một thư mục với tên thư mục là TIN<số báo danh>. Ví dụ: thí sinh có số báo danh là 01234 thì tên thư mục là TIN01234.

Hãy lập trình giải 2 bài toán sau:

Bài 1. Che mát cho vườn (10 điểm)

Vua có khu vườn hình bàn cờ với M hàng và N cột. Mỗi ô đặt một cây, mỗi cây có chiều cao riêng. Vua đưa cho trạng Tí các tấm lợp vuông kích thước 2x2 để làm mái lọng và yêu cầu Tí bố cục lại khu vườn, đặt các cây chống mái lọng che mát cho toàn bộ khu vườn.

Đầu tiên, Tí quy hoạch vườn thành từng cụm nhỏ với kích thước 2x2 vừa với một tấm lợp. Các cụm được đánh số tăng dần theo thứ tự từ trên xuống dưới và từ trái qua phải. Phần ở bìa dưới và bìa phải của khu vườn nếu không đủ kích thước vẫn được tính là một cụm. Ví dụ: khu vườn có kích thước 3x5 được quy hoạch thành 6 cụm theo thứ tự:

1	3	5
2	4	6

Tiếp theo, Tí sắp xếp lại cây trong vườn theo chiều cao cây giảm dần, đặt từ trên xuống dưới và từ trái qua phải trong từng cụm. Bắt đầu từ cụm 1, đặt xong sang cụm 2, … cho đến cụm cuối. Ví dụ:

Khu vườn 3x5 và chiều cao các cây ban đầu	Chiều cao các cây sau khi sắp xếp
1 3 4 9 1 8 2 6 5 3 5 8 5 2 1	9 8 5 3 1 8 6 4 3 1 5 5 2 2 1

Sau đó, Tí phải tính được chiều cao của các cây chống lọng. Cây chống lọng phải cao hơn chiều cao của cây cao nhất trong cụm đang che mát 1 đơn vị. Các cây chống lọng lắp đặt theo thứ tự cụm đã quy hoạch.

Tuy nhiên, nếu số hàng hoặc số cột của khu vườn là số lẻ thì các cụm ở bìa dưới hoặc bìa phải của khu vườn sẽ có phần mái lọng che luôn cả những cây ở hàng liền trên hoặc ở cột kế bên. Lúc này, khả năng sẽ có các tấm che chồng lên nhau. Nếu các cây chống lọng chồng lên nhau có chiều cao bằng nhau thì cây chống lọng lắp đặt sau phải tăng chiều cao thêm 1 đơn vị. Ví dụ xét khu vườn sau khi sắp xếp lại các cây:

8 5
8 3
2 1

Khu vườn cần đặt 2 cây chống lọng như sau:

• Cây chống lọng thứ nhất cao 9 (do che 4 cây có chiều cao: 8, 8, 5, 3 → chiều cao cây chống lọng thứ nhất là 8 + 1 = 9).
• Cây chống lọng thứ hai cao 10 (do che 4 cây có chiều cao: 8, 2, 3, 1 → chiều cao cây chống lọng thứ hai ban đầu là 8 + 1 = 9 nhưng do chồng lên cây chống lọng thứ nhất nên có chiều cao là 9 + 1 = 10).

Yêu cầu: Em hãy giúp trạng Tí sắp xếp lại vườn, cho biết số lượng tấm lợp lọng cần dùng và chiều cao của từng cây chống lọng.

Dữ liệu vào: Từ tập tin văn bản CHEVUON.INP, gồm:

• Dòng đầu tiên ghi 2 số nguyên dương M, N (2 ≤ M, N ≤ 10³) tương ứng với số hàng và cột của vườn.
• M dòng tiếp theo, mỗi dòng ghi N số nguyên dương cho biết chiều cao của cây tại vị trí hàng i, cột j (1 ≤ Aᵢⱼ ≤ 100).

Kết quả: Ra tập tin văn bản CHEVUON.OUT, gồm:

• M dòng đầu tiên mỗi dòng ghi N số nguyên dương lần lượt là chiều cao của các cây trong khu vườn sau khi đã sắp xếp lại.
• Dòng kế cuối ghi một số nguyên dương K cho biết số tấm lợp lọng cần dùng.
• Dòng cuối cùng ghi K số nguyên dương tương ứng với chiều cao của K cây chống lọng theo thứ tự cụm đã đánh số.

Lưu ý: Các số trên cùng dòng cách nhau một khoảng trắng.

Ví dụ:

CHEVUON.INP	CHEVUON.OUT
2 2 3 6 5 4	6 4 5 3 1 7
3 2 1 3 8 2 5 8	8 5 8 3 2 1 2 9 10

Bài 2. Đếm từ trùng lắp (10 điểm)

Nhìn vào văn bản đã soạn thảo, Tí thấy có nhiều điểm khá thú vị nên đưa ra khái niệm “Từ trùng lắp” là từ chỉ chứa các kí tự trong bảng chữ cái tiếng Anh (không phân biệt hoa thường) được phân cách bởi kí tự trống và có dạng như sau:

• Dạng thứ nhất: một từ có ít nhất 2 ký tự giống nhau thì được tính là một từ trùng lắp. Ví dụ: “chanh”, “Tat”, “nen”, …
• Dạng thứ hai: hai từ liền kề giống nhau thì được tính là một từ trùng lắp. Ví dụ: “Xinh xinh”, “ao ao”, …

Yêu cầu: Em hãy viết chương trình tìm các từ trùng lắp có trong văn bản theo định nghĩa của Tí.

Dữ liệu vào: Từ tập tin văn bản DEMTUTL.INP, ghi văn bản dài tối đa 255 ký tự trong bảng mã ASCII, văn bản có thể trên nhiều dòng.

Kết quả: Ra tập tin văn bản DEMTUTL.OUT, gồm:

• Dòng đầu tiên ghi một số nguyên N cho biết số lượng từ trùng lắp có trong văn bản.
• Dòng thứ hai ghi lại các từ trùng lắp theo thứ tự xuất hiện từ đầu đến cuối của văn bản (nếu có), mỗi từ cách nhau một khoảng trắng.

Ví dụ:

DEMTUTL.INP	DEMTUTL.OUT
Chuc mung nam moi!	1 Chuc
Con chim xanh xanh No dau canh chanh	2 xanh xanh chanh

---

Giám thị không giải thích gì thêm