16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án)

 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
Bài 3: Xổ Số (7 điểm)
 Hội xuân tại trường năm nay có gian hàng xổ số trúng điểm thưởng. Có N phiếu, mỗi 
phiếu có một mặt giống nhau, mặt còn lại ghi một số nguyên không âm ngẫu nhiên. Ban đầu 
mặt ghi số được đặt úp xuống mặt bàn. Người chơi được chọn K phiếu bất kỳ và nhận được 
số điểm thưởng là số lớn nhất trong K phiếu trên. Hùng rất hào hứng với trò chơi này và 
muốn biết tổng điểm thưởng mình được nhận là bao nhiêu nếu Hùng thử hết tất cả các cách 
chọn.
 Gọi S là tổng điểm thưởng được nhận nếu Hùng thử hết tất cả các cách chọn phiếu. 
Xét ví dụ với N = 4, K = 2 và giá trị của các phiếu lần lượt là 6, 7, 6, 5 thì Hùng có 6 cách 
chọn và tổng điểm thưởng S là 39, giá trị điểm thưởng của từng cách được cho trong bảng 
sau:
 Cách Giá trị của phiếu chọn Điểm thưởng
 Cách 1: chọn phiếu thứ 1, thứ 2 6, 7 7
 Cách 2: chọn phiếu thứ 1, thứ 3 6, 6 6
 Cách 3: chọn phiếu thứ 1, thứ 4 6, 5 6
 Cách 4: chọn phiếu thứ 2, thứ 3 7, 6 7
 Cách 5: chọn phiếu thứ 2, thứ 4 7, 5 7
 Cách 6: chọn phiếu thứ 3, thứ 4 6, 5 6
Yêu cầu: Hãy viết một chương trình cho biết phần dư khi chia S cho 109+7.
Dữ liệu: Vào từ file văn bản XOSO.INP dòng đầu chứa hai số nguyên N và K. Dòng thứ hai 
 6
chứa N số nguyên Xi, (0 < Xi < 10 ) lần lượt cho biết giá trị của N phiếu.
Kết quả: Ghi ra file văn bản XOSO.OUT trên một dòng là phần dư khi chia S cho 109+7.
Ràng buộc:
- 30% test ứng với 30% số điểm của bài có N ≤ 1000 và 1 ≤ K ≤ 3
- 20% test ứng với 20% số điểm của bài có N ≤ 25 và 1 ≤ K ≤ 12
- 50% test ứng với 50% số điểm của bài có N ≤ 100 000 và 1 ≤ K ≤ 50 
Ví dụ:
 XOSO.INP XOSO.OUT
4 2 39
6 7 6 5
 -------------HẾT-------------
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
 ĐÁP ÁN
Bài 1: Trung Bình Cộng (6 điểm)
Code C++:
#include 
#include 
#include 
#include 
using namespace std;
int main() {
 ifstream infile("TBC.INP");
 ofstream outfile("TBC.OUT");
 int N;
 infile >> N;
 vector A(N);
 vector B(N);
 // Đọc mảng A
 for (int i = 0; i < N; ++i) {
 infile >> A[i]; 
 }
 // Đọc mảng B
 for (int i = 0; i < N; ++i) {
 infile >> B[i];
 }
 // Tính trung bình cộng của mảng B
 double sumB = 0;
 for (int i = 0; i < N; ++i) {
 sumB += B[i];
 }
 double averageB = sumB / N;
 // xuất kết quả
 outfile << fixed << setprecision(2) << averageB;
 infile.close();
 outfile.close();
 return 0;
}
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
Bài 2: Mật Thư (7 điểm)
Code C++:
#include 
#include 
#include 
using namespace std;
string encrypt(const string &text, int k) {
 string result;
 for (char ch : text) {
 if (isalpha(ch)) {
 char base = islower(ch) ? 'a' : 'A';
 result += char((ch - base + K) % 26 + base);
 } else {
 result += ch; // Giữ nguyên ký tự không phải chữ cái
 }
 }
 return result;
}
int main() {
 ifstream infile("MATTHU.INP");
 ofstream outfile("MATTHU.OUT");
 string text;
 int K;
 getline(infile, text);
 infile >> K;
 string encryptedText = encrypt(text, K);
 outfile << encryptedText;
 infile.close();
 outfile.close();
 return 0;
}
Bài 3: Xổ Số (7 điểm)
#include 
#include 
#include 
#include 
using namespace std;
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
int main() {
 ifstream infile("XOSO.INP");
 ofstream outfile("XOSO.OUT");
 int N, K;
 infile >> N >> K;
 vector numbers(N);
 for (int i = 0; i < N; ++i) {
 infile >> numbers[i];
 }
 // săp xëp máng
 sort(numbers.begin(), numbers.end());
 // Tính tổng của K số lớn nhất
 int sum = 0;
 for (int i=N -K; i < N; ++i) {
 sum += numbers[i];
 }
 // xuất kết quả
 outfile << sum;
 infile.close();
 outfile.close();
 return 0;
}
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
 ĐỀ SỐ 4
 ĐỀ THI HỌC SINH GIỎI LỚP 9 THCS
 Thành phố: Hồ Chí Minh - Năm 2023
 Môn: TIN HỌC
 Tổng quan đề thi
Bài Tên bài File CT File input File output Điểm
 1 Trung bình cộng TBC.* TBC.INP TBC.OUT
 2 Mật mã MATMA.* MATMA.INP MATMA.OUT
 3 Xổ số XOSO.* XOSO.INP XOSO.OUT
(* là pas, cpp hoặc py)
Bài 1. TBC1 Trung bình cộng
Cho 2 mảng A, B có n phần tử. Phần tử B[i] là trung bình cộng của i phần tử đầu tiên của 
mảng A. Cho các giá trị của mảng B, tìm mảng A.
Input:
- Dòng đầu: số nguyên n (1 ≤ n ≤ 106)
 9
- Dòng thứ hai ghi b số nguyên b1 b2 ... bn của mảng B. (|bi| ≤ 10 ) 
Output: Ghi n số là các phần tử của mảng A
 Input Output
5 15 25 -25 45 90
15 20 5 15 30
Bài 2. MATMA Mật mã
Cho một xâu gồm n ký tự, trong đó có m ký tự #, mỗi ký tự # như vậy sẽ được thay thế bởi 1 
trong k ký tự (trong input sẽ cho). Tìm chuỗi có thứ tự từ điển bé thứ x.
Input:
- Dòng đầu: 4 số nguyên n, m, k, x. (1 ≤ n ≤500; 1 ≤ x, m ≤ n; 1 ≤ k ≤ 26)
- Dòng thứ hai: xâu n ký tự.
- m dòng tiếp theo, mỗi dòng chứa k ký tự là những phương án thay thế ký tự # thứ ỉ.
Output: ghi chuỗi có thứ tự từ điển bé thứ x. 
 Input Output Giải thích
16 3 2 6 programmingisfun Sau khi thế và sắp xếp thì có 8 xâu như sau:
pro#ramm#ngis#un 1.proarammingiseun
ag 2. proarammingisfun
iy 3. proarammyngiseun
ef 4. proarammyngisfun
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
 5. programmingiseun
 6. programmingisfun
 7. programmyngiseun
 8. programmyngisfun
Bài 3. SOXO Xổ số
Cho một mảng A có n phần tử, xét tất cả các đoạn con (không liên tiếp) có K phần tử của A, 
tính tổng của các số lớn nhất của các đoạn con này và modulo 109 + 7.
Input:
- Dòng đầu: 2 số nguyên n, K (1 ≤ n ≤ 105; 1 ≤ K ≤ 50)
 6
- Dòng thứ hai: mảng A. (1 ≤ Ai ≤ 10 )
Output: ghi tổng tìm được
 Input Output
4 2 39
6 7 6 5
 -------------HẾT-------------
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
 ĐÁP ÁN
Bài 1. TBC1 Trung bình cộng
Code C++:
#include 
#include 
#include 
using namespace std;
int main() {
 ifstream infile("TBC.INP");
 ofstream outfile("TBC.OUT");
 int N;
 infile >> N;
 vector A(N);
 vector B(N);
 // Đọc mảng A
 for (int i=0; i<N; ++i) {
 infile >> A[i];
 }
 // Đọc mảng B
 for (int i=0; i<N; ++i) {
 infile >> B[i];
 }
 // Tính trung bình cộng của B
 double sumB = 0;
 for (int i = 0; i < N; ++i) {
 sumB += B[i];
 }
 double averageB = sumB / N;
 // Tìm phân tử gần nhất với trung bình cộng
 int closest = B[0];
 double minDiff = abs(B[0] - averageB);
 for (int i = 1; i < N; ++i) {
 double diff = abs(B[i] - averageB);
 if (diff < minDiff) {
 minDiff = diff;
 closest = B[i];
 }
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
 }
 // xuất kết quả
 outfile << closest;
 infile.close();
 outfile.close();
 return 0;
}
Bài 2. MATMA Mật mã
Code C++:
#include 
#include 
#include 
using namespace std;
int main() {
 ifstream infile("MATMA.INP");
 ofstream outfile("MATMA.OUT");
 string input;
 infile >> input;
 // xóa các ký tự không phải chữ cái
 string result;
 for (char ch : input) {
 if (isalpha(ch)) {
 result += ch;
 }
 }
 // xuất kết quả
 outfile << result;
 infile.close();
 outfile.close();
 return 0;
}
Bài 3. SOXO Xổ số
Code C++:
#include 
#include 
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
#include 
#include 
using namespace std;
int main() {
 ifstream infile("SXXO.INP");
 ofstream outfile("SXXO.OUT");
 int N, K;
 infile >> N >> K;
 vector numbers(N);
 for (int i = 0; i < N; ++i) {
 infile >> numbers[i];
 }
 // sắp xếp mảng
 sort(numbers.begin(), numbers.end());
 // Tính tổng của K số lớn nhất
 int sum = 0;
 for (int i=N - K; i < N; ++i) {
 sum += numbers[i];
 }
 // xuất kết quả
 outfile << sum;
 infile.close();
 outfile.close();
 return 0;
}
 DeThiHay.net 16 Đề thi Học sinh giỏi các cấp môn Tin học 9 - TP.HCM (Có đáp án) - DeThiHay.net
 ĐỀ SỐ 5
 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 2021-2022
 ĐỀ 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 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. Ví dụ: thí sinh có số báo danh là 1234 thì tên thư mục là TIN 1234.
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 < 109). 
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 < 104
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. 
 DeThiHay.net