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

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 30.3.2022
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ập tin chương trình	Tập tin dữ liệu	Tập tin kết quả
SỐ ĐỘC LẬP	SODOCLAP.*	SODOCLAP.INP	SODOCLAP.OUT
LÀM VIỆC NHÀ	VIECNHA.*	VIECNHA.INP	VIECNHA.OUT
CHỌN QUÀ	CHONQUA.*	CHONQUA.INP	CHONQUA.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à 1234 thì tên thư mục là TIN1234.

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

Bài 1. Số độc lập (6 điểm)

Tí gọi số độc lập là những số nguyên dương có các chữ số đôi một khác nhau (hay nói cách khác là số nguyên dương có các chữ số không xuất hiện hơn một lần). Ví dụ 2019 là một số độc lập. Em của Tí rất thích các trò chơi toán học. Thế là, Tí đưa ra một số nguyên dương X, em sẽ tìm số độc lập nhỏ nhất mà lớn hơn X. Bạn hãy giúp Tí kiểm tra kết quả nhé.

Yêu cầu: Cho một số nguyên X, viết chương trình tìm số độc lập nhỏ nhất mà lớn hơn X.

Dữ liệu: Vào từ tập tin văn bản SODOCLAP.INP, gồm một số nguyên X (10 < X < 10⁹).

Kết quả: Ghi ra tập tin văn bản SODOCLAP.OUT một số nguyên dương là số độc lập nhỏ nhất mà lớn hơn X.

Ràng buộc: 50% test ứng với 50% số điểm của bài có 10 < X < 10⁴.

Ví dụ:

SODOCLAP.INP	SODOCLAP.OUT
2022	2031

Bài 2. Làm việc nhà (7 điểm)

Bình hay giúp đỡ ba mẹ làm việc nhà. Để đảm bảo việc học, Bình chỉ có thể sắp xếp được một lượng thời gian T để làm việc nhà. Bình lên danh sách những việc nhà mình có thể làm, đi kèm với thời gian cần để thực hiện xong việc đó. Các việc nhà trên có thể thực hiện theo thứ tự bất kỳ nhưng tại một thời điểm chỉ có thể thực hiện một việc nhất định. Bình đang tìm cách làm sao để có thể thực hiện xong nhiều nhất các việc nhà trong danh sách của mình.

Yêu cầu: Cho các việc nhà và thời gian cần để hoàn thành công việc đó. Bạn hãy viết chương trình cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian T.

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

• Dòng đầu tiên chứa một số nguyên T (0 ≤ T ≤ 10⁹) là giới hạn thời gian.
• Dòng thứ hai chứa một số nguyên C (0 ≤ C ≤ 100) là số lượng việc nhà.
• C dòng tiếp theo, mỗi dòng chứa một số nguyên dương cho biết thời gian cần để thực hiện xong một việc nhà trong danh sách. Giả sử thời gian tối đa để thực hiện một việc nhà là 10⁹.

Kết quả: Ghi ra tập tin văn bản VIECNHA.OUT một số nguyên cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian T.

Ràng buộc: 50% test ứng với 50% số điểm của bài có 0 ≤ T ≤ 10⁴ và thời gian tối đa để thực hiện một công việc là 10⁴.

Ví dụ:

VIECNHA.INP	VIECNHA.OUT
6 3 3 6 3	2

Bài 3. Chọn quà (7 điểm)

Để khích lệ học sinh tích cực học tập, cô giáo lớp An dùng các nhãn dán khen thưởng khi tổ chức các hoạt động trên lớp. Cuối năm, cô khen thưởng cho các bạn tích lũy được nhiều nhãn. Với sự nỗ lực, An đã tích lũy được K nhãn.

Cô chuẩn bị một khung lưới hình chữ nhật có kích thước D × R. Khung lưới này có D đường ngang và R đường dọc tạo thành (D − 1) × (R − 1) hình vuông nhỏ có chiều dài cạnh là 1 đơn vị. Các món quà được treo tại các mối nối giao nhau của những đường ngang và đường dọc trên lưới. Tại một mối nối có thể không có quà hoặc có nhiều nhất một món quà.

Để nhận quà, An được phát cho một khung vợt hình vuông có kích thước K × K (cách tính đơn vị như khung lưới). An đặt vợt trên khung lưới sao cho 4 cạnh của vợt phải nằm hoàn toàn trên các đường ngang, đường dọc của khung lưới. Khi đó An sẽ nhận các món quà nằm hoàn toàn bên trong 4 cạnh của vợt (các món quà nằm trên cạnh của vợt sẽ không được tính). Bạn hãy giúp An xác định số lượng lớn nhất các món quà mà An có thể nhận.

Yêu cầu: Viết chương trình cho biết số lượng món quà lớn nhất mà An có thể nhận khi đặt vợt trên khung lưới.

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

• Dòng đầu tiên chứa 3 số nguyên D, R, K (3 ≤ K ≤ D, R ≤ 1000) cách nhau một khoảng trắng.
• Trên D dòng tiếp theo, mỗi dòng chứa R kí tự mô tả hình ảnh khung lưới với các món quà treo trên đó. Kí tự * cho biết vị trí một món quà, kí tự . cho biết vị trí một mối nối trên khung lưới.

Kết quả: Ghi ra tập tin văn bản CHONQUA.OUT một số nguyên cho biết số lượng món quà lớn nhất mà An có thể nhận khi đặt vợt trên khung lưới để nhận quà.

Ràng buộc: 50% test ứng với 50% số điểm của bài có 3 ≤ D, R ≤ 100.

Ví dụ:

CHONQUA.INP	CHONQUA.OUT
7 6 4 ...... .*.*.* ...... .*.*.. ..*... ..*... *....*	2

Chú thích: Hình minh họa một cách đặt vợt giúp An lấy tối đa 2 món quà. Lưu ý không tính những món quà nằm trên cạnh của vợt.

......
.*.*.*
+--+..
|*.|..
|.*|..
+--+..
*....*

Chú ý

Khung lưới trong ví dụ được chép từ ảnh chụp đề thi (khá mờ). Nếu có chỗ chưa khớp, hãy đối chiếu với hình minh họa ở trên.

---

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