Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án)

 Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
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 < 109) 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à 109. 
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 ≤ 104 và thời gian tối đa để thực 
hiện một công việc là 104.
Ví dụ:
 VIECNHA.INP VIECNHA.OUT
6 2
3
3
6
3
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 x R. Khung lưới này có D 
đường ngang và R đường dọc tạo thành (D-1) x (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 x 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 
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
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 CHÚ THÍCH
7 6 4 2 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
.*.*.. |.*|.. 
..* +--+.. 
..* * .*
* .*
 -------------HẾT-------------
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
 ĐÁP ÁN
Bài 1: SỐ ĐỘC LẬP (6 điểm)
Code: C++
#include 
#include 
using namespace std;
bool isPalindrome(int number) {
 int original = number, reversed = 0;
 while (number > 0) {
 reversed = reversed * 10 + number % 10;
 number /= 10;
 }
 return original == reversed;
}
int main() {
 ifstream infile("SODOCLAP.INP");
 ofstream outfile("SODOCLAP.OUT");
 int L, R;
 infile >> L >> R;
 int count = 0;
 for (int i = L; i <= R; ++i) {
 if (isPalindrome(i)) {
 count++;
 }
 }
 outfile << count;
 infile.close();
 outfile.close();
 return 0;
}
Bài 2: LÀM VIỆC NHÀ (7 điểm)
Code: C++
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
#include 
#include 
#include 
#include 
using namespace std;
int main() {
 ifstream infile("VIECNHA.INP");
 ofstream outfile("VIECNHA.OUT");
 int N;
 infile >> N;
 vector workTimes(N);
 for (int i = 0; i < N; ++i) {
 infile >> workTimes[i];
 }
 // Sắp xếp thời gian làm việc
 sort(workTimes.begin(), workTimes.end());
 // Tính tổng thời gian làm việc nhà
 int totalIdleTime = 0;
 for (int i = 1; i < N; ++i) {
 totalIdleTime += workTimes[i] - workTimes[i - 1];
 }
 // xuất kết quả
 outfile << totalIdleTime;
 infile.close();
 outfile.close();
 return 0;
}
Bài 3: CHỌN QUÀ (7 điểm)
Code: C++
#include 
#include 
#include 
#include 
using namespace std;
int main() {
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
 ifstream infile("CHONQUA.INP");
 ofstream outfile("CHONQUA.OUT");
 int N, X;
 infile >> N >> X;
 vector values(N);
 for (int i = 0; i < N; ++i) {
 infile >> values[i];
 }
 // Sắp xếp giá trị
 sort(values.begin(), values.end());
 int totalvalue = 0;
 for (int i = 0; i < X && i < N; ++i) {
 totalValue += values[i];
 }
 outfile << totalValue;
 infile.close();
 outfile.close();
 return 0;
}
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
 ĐỀ SỐ 6
 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI LỚP 9 THCS
 THÀNH PHỐ HỒ CHÍ MINH NĂM HỌC 2020-2021
 ĐỀ CHÍNH THỨC Môn thi: Tin học
 (Đề thi gồm 02 trang) Thời gian: 120 phút (không kể thời gian giao đề)
 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 CHE VUON.* 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 . 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 3 x 5 Được quy hoạch thành 6 cụm theo thứ tự
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ụ:
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
Khu vườn có kích thước 3 x 5 Chiều cao các cây sau khi sắp xếp
và chiều cao các cây ban đầu
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ài 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 như hình dưới.
 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 cạo 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 ≤ 103) 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 ≤ Aij ≤ 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 
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
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 CHEVUON.INP CHEVUON.OUT
2 2 6 4 3 2 8 5
3 6 5 3 1 3 8 3
5 4 1 8 2 2 1
 7 5 8 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ì dượ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 dầ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 2
No dau canh chanh xanh xanh chanh
 -------------HẾT-------------
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
 ĐÁP ÁN
Bài 1: CHE MÁT CHO VƯỜN (10 điểm)
#include // Để nhập xuất dữ liệu
#include // Để sử dụng std::vector
#include // Để sử dụng std::sort
int main() {
 // Chuyển hướng nhập xuất từ console sang file theo yêu cầu của đề bài
 freopen("CHEVUON.INP", "r", stdin); // Mở file input
 freopen("CHEVUON.OUT", "w", stdout); // Mở file output
 // Tối ưu hóa hiệu suất nhập xuất trong C++
 std::ios_base::sync_with_stdio(false);
 std::cin.tie(NULL);
 std::cout.tie(NULL);
 int M, N; // Kích thước của khu vườn M x N
 std::cin >> M >> N;
 std::vector heights; // Vector để lưu trữ tất cả các chiều cao cây
 // Đọc tất cả chiều cao cây từ input và lưu vào vector
 for (int i = 0; i < M; ++i) {
 for (int j = 0; j < N; ++j) {
 int h;
 std::cin >> h;
 heights.push_back(h);
 }
 }
 // Sắp xếp các chiều cao cây theo thứ tự giảm dần
 // std::sort với std::greater () để sắp xếp giảm dần
 std::sort(heights.begin(), heights.end(), std::greater ());
 // In ra ma trận mới với các chiều cao đã sắp xếp
 // Duyệt qua vector và in ra N phần tử mỗi hàng
 for (int i = 0; i < M; ++i) {
 De-Thi.com Tài liệu luyện thi HSG Tin học Lớp 9 TP.HCM (15 Đề Kèm đáp án) - De-Thi.com
 for (int j = 0; j < N; ++j) {
 // In phần tử hiện tại
 std::cout << heights[i * N + j];
 // Nếu không phải là phần tử cuối cùng của hàng, in một khoảng trắng
 if (j < N - 1) {
 std::cout << " ";
 }
 }
 // Sau mỗi hàng, xuống dòng
 std::cout << std::endl;
 }
 return 0;
}
Bài 2: ĐẾM TỪ TRÙNG LẶP (10 điểm)
#include // Để nhập xuất dữ liệu
#include // Để làm việc với chuỗi
#include // Để sử dụng std::vector
#include // Để sử dụng std::transform, std::sort (nếu cần)
#include // Để phân tách từ từ dòng
#include // Để lưu trữ các từ duy nhất đã được thêm vào kết quả
 // Hàm chuyển đổi chuỗi sang chữ thường
 std::string toLower(std::string s) {
 std::transform(s.begin(), s.end(), s.begin(),
 [](unsigned char c){ return std::tolower(c); });
 return s;
 }
 // Hàm kiểm tra một từ có ít nhất 2 ký tự giống nhau không (Dạng 1)
 bool hasDuplicateChars(const std::string& word) {
 if (word.length() <= 1) { // Một từ có 0 hoặc 1 ký tự không thể có ký tự lặp
 return false;
 }
 std::vector char_counts(26, 0); // Đếm tần suất cho các chữ cái 'a' đến 'z'
 De-Thi.com