HSG lớp 9 Nghệ An 2025-2026 (Bảng A)

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN ĐỀ CHÍNH THỨC
Đề thi gồm 04 trang

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 Năm học 2025 - 2026
Môn thi: Tin học - Bảng A
Thời gian làm bài: 150 phút (không kể thời gian giao đề)

---

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Thời gian	Bộ nhớ
Tích hai số nguyên tố khác nhau	TICHSO.*	TICHSO.INP	TICHSO.OUT	1 giây	1024MB
Dàn đèn	DANDEN.*	DANDEN.INP	DANDEN.OUT	1 giây	1024MB
Đóng gói sản phẩm	SANPHAM.*	SANPHAM.INP	SANPHAM.OUT	1 giây	1024MB
Chọn xâu con	CHONXAU.*	CHONXAU.INP	CHONXAU.OUT	1 giây	1024MB

Phần mở rộng .* được thay thế bằng Sb2, Sb3, Cpp, Py ứng với các ngôn ngữ lập trình Scratch, C++, Python.

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

Câu 1. Tích hai số nguyên tố khác nhau (6.0 điểm)

Alice và Bob đang cùng nhau ôn tập để chuẩn bị cho một kì thi lập trình. Bài toán lập trình mà hai bạn đang làm như sau:

Cho số nguyên dương n (n ≤ 10⁶), tìm số lượng các số nguyên dương x sao cho:

• x là tích của hai số nguyên tố khác nhau, tức là x = p × q với p, q là hai số nguyên tố và p ≠ q.
• x không lớn hơn n, tức là x ≤ n.

Bạn cũng đang tham gia kì thi lập trình danh giá cấp tỉnh, hãy lập trình để đưa ra kết quả đúng của bài toán.

Dữ liệu cho từ tệp văn bản TICHSO.INP gồm một số nguyên dương n (n ≤ 10⁶).

Kết quả ghi ra tệp văn bản TICHSO.OUT gồm một số nguyên là kết quả đúng của bài toán trên.

Ví dụ:

TICHSO.INP	TICHSO.OUT	Giải thích
10	2	Có 2 giá trị x thoả mãn đó là: ○ x = 6 = 2 × 3 ○ x = 10 = 2 × 5

Giới hạn:

• Có 80% số test với 1 ≤ n ≤ 10³;
• Có 20% số test với 10³ < n ≤ 10⁶.

Câu 2. Dàn đèn (5.0 điểm)

Sau khi hoàn thành bài thi, Alice, Bob cùng các bạn thi lập trình tham quan trải nghiệm tại công viên ánh sáng. Công viên có một dàn đèn gồm n bóng đèn được đặt vị trí theo phương nằm ngang. Các đèn đánh số thứ tự từ 1 đến n theo hướng từ trái sang phải. Mỗi bóng đèn có ánh sáng màu xanh hoặc màu đỏ.

Nhìn vào dàn đèn với ánh sáng màu xanh, màu đỏ rực rỡ, Alice đã yêu cầu Bob trả lời câu hỏi:

Nếu phải chọn k bóng đèn kề nhau và đổi trạng thái màu của các bóng đèn đó (màu xanh chuyển sang màu đỏ, màu đỏ chuyển sang màu xanh) thì số lượng bóng đèn màu xanh trên dàn đèn nhiều nhất là bao nhiêu?

Yêu cầu: Hãy đưa ra câu trả lời đúng của Bob.

Dữ liệu cho từ tệp văn bản DANDEN.INP gồm:

• Dòng thứ nhất ghi hai số nguyên dương n, k (3 ≤ n ≤ 10⁶; 1 ≤ k ≤ n).
• Dòng thứ hai ghi n số nguyên a₁, a₂, …, aₙ, 0 ≤ aᵢ ≤ 1, trong đó, aᵢ = 0 biểu thị đèn i có ánh sáng màu đỏ, aᵢ = 1 biểu thị đèn i có ánh sáng màu xanh.

Kết quả ghi ra tệp văn bản DANDEN.OUT gồm một số nguyên là số lượng bóng đèn màu xanh nhiều nhất có thể đạt được khi chọn k bóng đèn kề nhau và đổi màu sáng của k bóng đèn được chọn.

Ví dụ:

DANDEN.INP	DANDEN.OUT	Giải thích
8 2 1 1 0 0 0 1 1 0	6	Có 8 bóng đèn, hiện tại bóng đèn thứ 3 và thứ 4 đang màu đỏ. Nếu chọn 2 đèn này và chuyển sang màu xanh, thì trạng thái màu sắc của 8 đèn là: 1, 1, 1, 1, 0, 1, 1, 0. Số lượng bóng đèn sáng màu xanh là 6. Đây là số lượng đèn màu xanh lớn nhất có thể đạt được khi chọn 2 bóng đèn kề nhau và đổi màu của chúng.
8 2 1 1 1 1 1 1 1 1	6	Hiện tại tất cả 8 bóng đèn đều có màu xanh. Nếu chọn 2 đèn kề nhau và chuyển thành màu đỏ thì số đèn màu xanh còn lại là 6.
8 1 1 0 1 0 1 0 1 1	6	Hiện tại có 5 đèn màu xanh và 3 đèn màu đỏ. Nếu chọn đèn thứ 2 và chuyển sang màu xanh thì có 6 đèn màu xanh.

Giới hạn:

• Có 40% số test ứng với k = 1;
• Có 40% số test ứng với k = 2;
• Có 20% số test còn lại không có giới hạn gì thêm.

Câu 3. Đóng gói sản phẩm (5.0 điểm)

Công ty của gia đình Alice có n sản phẩm với khối lượng lần lượt là a₁, a₂, …, aₙ. Công ty sẽ đóng gói thành các kiện hàng để gửi cho khách. Mỗi kiện hàng có đúng k sản phẩm và khối lượng của các kiện hàng đều bằng nhau. Khối lượng của một kiện hàng bằng tổng khối lượng của k sản phẩm trong kiện hàng đó. Chú ý là, một sản phẩm thuộc nhiều nhất một kiện hàng.

Alice muốn biết Công ty của gia đình mình có thể đóng gói được nhiều nhất bao nhiêu kiện hàng.

Dữ liệu cho từ tệp văn bản SANPHAM.INP gồm:

• Dòng đầu tiên ghi hai số nguyên dương n, k (1 ≤ k ≤ 3; 1 ≤ n ≤ 10⁵).
• Dòng thứ hai ghi n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 1000).

Kết quả ghi ra tệp văn bản SANPHAM.OUT gồm một số nguyên là số lượng kiện hàng nhiều nhất có thể đóng gói được.

Ví dụ:

SANPHAM.INP	SANPHAM.OUT	Giải thích
5 1 1 6 6 4 6	3	Đóng gói được nhiều nhất 3 kiện hàng, mỗi kiện hàng gồm 1 sản phẩm. Đó là các sản phẩm thứ 2, 3, 5. Các sản phẩm này đều có khối lượng bằng 6.
5 2 1 6 6 4 6	1	Đóng gói được nhiều nhất một kiện hàng gồm 2 sản phẩm. Có thể lấy hai sản phẩm bất kì để đóng gói thành 1 kiện hàng.
10 3 1 2 3 3 2 2 2 1 1 1	3	Đóng gói được nhiều nhất 3 kiện hàng, mỗi kiện hàng gồm 3 sản phẩm. Cụ thể, 3 kiện hàng, mỗi kiện hàng gồm 3 sản phẩm có khối lượng như sau: {1, 2, 2} → tổng khối lượng bằng 5. {1, 2, 2} → tổng khối lượng bằng 5. {1, 1, 3} → tổng khối lượng bằng 5.

Giới hạn:

• Có 40% số test ứng với k = 1, n ≤ 1000;
• Có 40% số test ứng với k = 2;
• Có 20% số test ứng với k = 3, 1 ≤ aᵢ ≤ 3.

Câu 4. Chọn xâu con (4.0 điểm)

Bob có hai xâu kí tự A và B gồm các chữ cái latin thường. Theo hướng từ chỉ số nhỏ đến chỉ số lớn của các kí tự, Bob sẽ lần lượt chọn đúng k xâu con khác rỗng (xâu con gồm các kí tự kề nhau) của xâu A và không giao nhau. Sau đó ghép những xâu này theo thứ tự được chọn để tạo thành một xâu mới.

Bob muốn biết có bao nhiêu cách chọn như vậy để xâu mới nhận được bằng xâu B?

Bạn hãy lập trình để tìm kết quả giúp Bob nhé.

Dữ liệu cho trong tệp văn bản CHONXAU.INP gồm:

• Dòng thứ nhất gồm ba số nguyên dương n, m, k, lần lượt là: độ dài xâu A; độ dài xâu B và số xâu con cần chọn.
• Dòng thứ hai gồm một xâu độ dài n là xâu A.
• Dòng thứ ba gồm một xâu độ dài m là xâu B.

Kết quả ghi ra tệp văn bản CHONXAU.OUT gồm một số nguyên là giá trị khi lấy số lượng cách chọn chia lấy dư cho 10⁹ + 7.

Ví dụ:

CHONXAU.INP	CHONXAU.OUT	Giải thích
6 3 1 aabaab aab	2	k = 1: Có 2 cách chọn: → (aab)aab → aab(aab)
6 3 2 aabaab aab	7	k = 2: Có 7 cách chọn: → (a)(ab)aab → (a)aba(ab) → a(a)ba(ab) → (aa)(b)aab → (aa)baa(b) → aab(a)(ab) → aab(aa)(b)

Giới hạn:

• Có 25% số test ứng với k = 1, 1 ≤ n ≤ 1000, 1 ≤ m ≤ 100, 1 ≤ k ≤ m ≤ n;
• Có 25% số test ứng với k = 2, 1 ≤ n ≤ 1000, 1 ≤ m ≤ 100, 1 ≤ k ≤ m ≤ n;
• Có 25% số test ứng với k ≥ 3, 1 ≤ n ≤ 1000, 1 ≤ m ≤ 100, 1 ≤ k ≤ m ≤ n;
• Có 25% số test còn lại ứng với k ≥ 3, 1000 < n ≤ 100000, 1 ≤ m ≤ 20, 1 ≤ k ≤ m ≤ n.

---

Hết