HSG lớp 9 Cà Mau 2023-2024

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH CÀ MAU Năm học 2023 - 2024

MÔN TIN HỌC 3 bài: DEMKITU, TROCHOI, SNT

---

Ghi chú

Đề được đánh máy lại theo tài liệu “50 đề thi HSG THCS” (không kèm phần tiêu đề, thời gian làm bài và thang điểm của đề gốc).

Bài 1. Đếm kí tự

Xâu là dãy liên tiếp các kí tự (bao gồm kí tự chữ Latinh, số và dấu cách).

Yêu cầu: Cho xâu S có N kí tự (chỉ chứa các kí tự chữ Latinh và in thường). Hãy đếm số lần xuất hiện của các kí tự có trong xâu S.

Dữ liệu vào: Từ tệp tin văn bản demkitu.inp gồm một dòng duy nhất chứa xâu S có N ký tự (1 ≤ N ≤ 10⁶).

Kết quả: Ghi ra tệp văn bản demkitu.out gồm nhiều dòng, mỗi dòng gồm hai kết quả lần lượt là kí tự và số lần xuất hiện của nó trong xâu S (các ký tự được sắp xếp theo thứ tự Alpha), hai kết quả được ngăn cách nhau bởi một khoảng trắng.

Ví dụ:

demkitu.inp	demkitu.out	Giải thích
dbakabk	a 2 b 2 d 1 k 2	Có 4 kí tự xuất hiện trong xâu S là a, b, d và k, với số lần xuất hiện: - Kí tự ‘a’: 2 lần; - Kí tự ‘b’: 2 lần; - Kí tự ‘d’: 1 lần; - Kí tự ‘k’: 2 lần.

Bài 2. Trò chơi dân gian

Trong buổi hội trại mừng ngày thành lập đoàn 26/3, ban tổ chức yêu cầu các đội tham gia một trò chơi tập thể. Có tất cả m câu hỏi và n đội chơi tham gia, với câu hỏi thứ i (1 ≤ i ≤ m), đội thứ j (1 ≤ j ≤ n) sẽ được ban giám khảo cho điểm là aᵢⱼ. Sau trò chơi, đội chiến thắng là đội có tổng số điểm của m câu hỏi là cao nhất.

Yêu cầu: Hãy giúp ban tổ chức tìm ra đội chiến thắng và tổng số điểm của đội đó?

Dữ liệu vào: Tệp tin văn bản trochoi.inp, gồm:

• Dòng đầu chứa hai số nguyên m và n (1 ≤ m, n ≤ 10³).
• m dòng sau, mỗi dòng chứa n số nguyên aᵢⱼ (1 ≤ aᵢⱼ ≤ 10⁶) thể hiện số điểm câu hỏi thứ i của đội thứ j, các số được ngăn cách nhau bởi một khoảng trắng.

Dữ liệu vào đảm bảo chỉ có duy nhất một đội chiến thắng.

Kết quả: Ghi ra tệp tin văn bản trochoi.out gồm một dòng duy nhất chứa hai số nguyên lần lượt là số thứ tự và tổng số điểm của đội chiến thắng (hai số ngăn cách nhau bởi một khoảng trắng).

Ví dụ:

trochoi.inp	trochoi.out	Giải thích
4 5 2 5 4 1 2 4 6 7 3 3 6 9 5 4 3 3 8 1 2 4	2 28	- Có 4 câu hỏi và 5 đội tham gia chơi - Số điểm 4 câu hỏi của đội 1 lần lượt là 2, 4, 6 và 3 → tổng điểm là 15 - Tương tự ta có tổng số điểm của đội 2, 3, 4, 5 lần lượt là 28, 17, 10 và 12. ⇒ Đội 2 là đội chiến thắng với 28 điểm.

Bài 3. Số nguyên tố

Số nguyên tố là số nguyên dương chỉ có duy nhất hai ước là 1 và chính nó. Ví dụ số 11 là số nguyên tố vì nó chỉ có hai ước là 1 và 11; số 15 không phải là số nguyên tố vì nó có 4 ước gồm 1, 3, 5, 15; số 1 không phải là số nguyên tố vì nó có 1 ước là 1.

Yêu cầu: Cho số nguyên N (1 ≤ N ≤ 10⁶) và N đoạn số nguyên [Lᵢ, Rᵢ] (1 ≤ Lᵢ < Rᵢ ≤ 10⁷; 1 ≤ i ≤ N). Hãy tìm số lượng số nguyên tố thuộc mỗi đoạn [Lᵢ, Rᵢ].

Dữ liệu vào: Từ tệp tin văn bản snt.inp, gồm:

• Dòng đầu tiên chứa số nguyên N.
• N dòng tiếp theo, dòng thứ i chứa hai số nguyên Lᵢ, Rᵢ (ngăn cách nhau bởi một khoảng trắng).

Kết quả: Ghi ra tệp tin văn bản snt.out gồm N dòng, dòng thứ i ghi một số nguyên là số lượng số nguyên tố thuộc đoạn [Lᵢ, Rᵢ].

Ví dụ:

snt.inp	snt.out	Giải thích
2 14 16 11 25	0 5	Số lượng số nguyên tố thuộc 2 đoạn tương ứng: - Đoạn [14, 16]: không có số nguyên tố; - Đoạn [11, 25]: có 5 số nguyên tố là 11, 13, 17, 19, 23.

Ràng buộc:

• Có 40% số test với 1 ≤ N ≤ 10³; 1 ≤ Lᵢ < Rᵢ ≤ 10³.
• Có 60% số test với 10³ ≤ N ≤ 10⁶; 1 ≤ Lᵢ < Rᵢ ≤ 10⁷.