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

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

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Năm học 2022 - 2023
Môn: Tin học - Ngày thi: 14/3/2023
Thời gian làm bài: 120 phút (không tính 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ả
Trung Bình Cộng	TBC.*	TBC.INP	TBC.OUT
Mật Thư	MATTHU.*	MATTHU.INP	MATTHU.OUT
Xổ Số	XOSO.*	XOSO.INP	XOSO.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. Trung Bình Cộng (6 điểm)

Tuấn thường hỗ trợ em An củng cố kiến thức bài học bằng cách cho em làm những bài luyện tập. Để ôn tập những phép tính cơ bản, Tuấn cho An bài toán tính trung bình cộng như sau. Cho một dãy số nguyên A có N phần tử, các phần tử được đánh số từ 1 đến N. An được yêu cầu tạo một dãy số nguyên B có N phần tử và phần tử thứ i của dãy B là trung bình cộng i số đầu tiên của dãy A. Ví dụ với dãy A là: 15, 25, −25, 25, 60 thì dãy B nếu được tạo đúng sẽ là: 15, 20, 5, 10, 20. An cũng thường thử thách anh Tuấn bằng những câu hỏi thú vị. Sau khi giải xong bài toán trung bình cộng của Tuấn, An liền đưa Tuấn đáp án là dãy số B và hỏi lại Tuấn xem anh có thể tạo lại dãy số A ban đầu từ dãy số B không.

Yêu cầu: Hãy viết chương trình giúp Tuấn tìm dãy số A từ dãy số B.

Dữ liệu: Vào từ file văn bản TBC.INP dòng đầu chứa một số nguyên N. Dòng thứ hai chứa N số nguyên Bᵢ (−10⁶ ≤ Bᵢ ≤ 10⁶) lần lượt cho biết giá trị của N phần tử dãy B.

Kết quả: Ghi ra file văn bản TBC.OUT trên một dòng N số nguyên lần lượt là N phần tử của dãy A. Có thể giả sử dữ liệu cho sẽ đảm bảo các giá trị phần tử dãy A là số nguyên.

Ràng buộc:

• 50% test ứng với 50% số điểm của bài có N ≤ 5
• 50% test ứng với 50% số điểm của bài có 5 < N ≤ 100 000

Ví dụ:

TBC.INP	TBC.OUT
5 15 20 5 10 20	15 25 -25 25 60

Bài 2. Mật Thư (7 điểm)

Khi đang đọc sách về các thuật toán sắp xếp trong một hiệu sách cũ, Tý vô tình phát hiện một mật thư và cả khóa để mở mật thư đó. Mật thư là một chuỗi có N kí tự. M kí tự trong chuỗi đã được mã hóa bằng kí tự ‘#’, các kí tự còn lại là kí tự chữ cái tiếng Anh viết thường. Khóa để mở mật thư là M xâu kí tự có cùng chiều dài K và một số nguyên X. Xâu thứ i cho biết kí tự ‘#’ thứ i trong mật thư có thể được thay thế bằng một trong K kí tự của xâu. Xét danh sách các xâu có thể được tạo sau khi thay M kí tự ‘#’ trong mật thư. Lưu ý những xâu trùng nhau nếu có sau khi thay kí tự ‘#’ cũng được đưa vào danh sách và danh sách này sẽ có Kᴹ xâu. Xâu thứ X sau khi sắp xếp các xâu trên tăng dần theo thứ tự từ điển cho ta lời giải của mật thư.

Yêu cầu: Hãy viết một chương trình cho biết lời giải của mật thư.

Dữ liệu: Vào từ file văn bản MATTHU.INP, dòng đầu chứa 4 số nguyên lần lượt là N, M, K, X (1 ≤ N ≤ 500, 1 ≤ M ≤ N, 1 < K ≤ 26, 1 ≤ X ≤ 10⁹). Dòng thứ hai là một xâu có N kí tự cho biết mật thư, xâu này có M kí tự ‘#’ và các chữ cái tiếng Anh viết thường. Dòng thứ i trong M dòng tiếp theo chứa K kí tự cho biết các kí tự có thể thay thế cho kí tự ‘#’ thứ i trong mật thư.

Kết quả: Ghi ra file văn bản MATTHU.OUT một dòng là lời giải của mật thư.

Ràng buộc:

• 30% test ứng với 30% số điểm của bài có M = 1 và 1 < K ≤ 3
• 20% test ứng với 20% số điểm của bài có M = 1 và 3 < K ≤ 26
• 50% test ứng với 50% số điểm của bài có 1 ≤ M ≤ 500 và 1 < K ≤ 26

Ví dụ:

MATTHU.INP	MATTHU.OUT	Giải thích
16 3 2 6 pro#ramm#ngis#un ag iv ef	programmingisfun	Danh sách các xâu sau khi sắp xếp, lời giải là xâu thứ 6: 1. proarammingiseun 2. proarammingisfun 3. proarammvngiseun 4. proarammvngisfun 5. programmingiseun 6. programmingisfun 7. programmvngiseun 8. programmvngisfun

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 10⁹ + 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 chứa N số nguyên Xᵢ (0 ≤ Xᵢ ≤ 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 10⁹ + 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 6 7 6 5	39

---

(Cán bộ coi thi không giải thích gì thêm)