HSG lớp 9 Nghệ An 2022-2023

ĐỀ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 TỈNH NGHỆ AN Năm học 2022 - 2023

MÔN TIN HỌC 4 bài: NTCN, HangCay, ChonBong, MatDo

---

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. Cặp số nguyên tố cùng nhau

Tuấn là một học sinh rất yêu thích Tin học. Ước mơ của cậu sau này là trở thành một lập trình viên tài năng. Tuấn thường xuyên tìm hiểu các thông tin, sự kiện liên quan đến Công nghệ. Một sự kiện công nghệ nổi tiếng trên toàn thế giới trong thời gian gần đây là sự ra mắt robot thông minh ChatGPT của công ty công nghệ OpenAI. Tuấn cũng rất tò mò về ChatGPT nên đã sử dụng để giải bài toán. Bài toán mà Tuấn đưa cho ChatGPT như sau:

Cho số nguyên dương n. Tìm số lượng các số nguyên dương X nhỏ hơn n thỏa mãn: X và n là hai số nguyên tố cùng nhau (tức là ước chung lớn nhất của X và n bằng 1).

Thật là thú vị, khi Tuấn nhập n = 5. ChatGPT đưa ra kết quả là: Có 4 số, cụ thể là các số: 1, 2, 3, 4.

Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của ChatGPT nhé.

Dữ liệu cho trong tệp văn bản NTCN.Inp gồm một số nguyên dương n (2 ≤ n ≤ 2×10⁹).

Kết quả ghi ra tệp văn bản NTCN.Out gồm một số nguyên duy nhất là số lượng các số nguyên dương x, nhỏ hơn n và nguyên tố cùng nhau với n.

Ví dụ:

ntcn.inp	ntcn.out	Giải thích
5	4	n = 5, trong 4 số 1, 2, 3, 4 nhỏ hơn n. Có 4 số thỏa mãn: x = 1, 2, 3, 4 là các số nguyên tố cùng nhau với n.
10	4	n = 10, trong 9 số: 1, 2, 3, 4, 5, 6, 7, 8, 9 nhỏ hơn n. Có 4 số thỏa mãn: x = 1, 3, 7, 9 là các số nguyên tố cùng nhau với n.

Giới hạn:

• Có 50% số test ứng với 50% số điểm thỏa mãn: 2 ≤ n ≤ 2000.
• Có 40% số test ứng với 40% số điểm thỏa mãn: 2000 < n ≤ 2×10⁶.
• Có 10% số test ứng với 10% số điểm thỏa mãn: 2×10⁶ < n ≤ 2×10⁹.

Bài 2. Hàng cây sân trường

Ngôi trường của Tuấn chuẩn bị kỉ niệm ngày thành lập trường. Nhà trường đã trồng một hàng cây xanh trông rất đẹp. Hàng cây gồm n cây xanh được đánh số thứ tự từ 1 đến n (theo hướng từ trái sang phải) và cách đều nhau, tức là khoảng cách giữa hai cây kề nhau là không đổi.

Để tưới nước cho cây, nhà trường có kế hoạch lắp đặt m (1 ≤ m ≤ n) vòi tưới nước tự động. Vòi nước thứ i (i = 1, 2, 3, …, m) được lắp tại vị trí cây thứ Xᵢ thì có thể tưới nước cho cây thứ Xᵢ và Rᵢ cây liền kề bên trái và Rᵢ cây liền kề bên phải vòi nước đó, tức là vòi thứ i sẽ tưới nước được cho cây thứ j nếu |j − Xᵢ| ≤ Rᵢ. Rᵢ được gọi là bán kính tưới nước của vòi thứ i.

Cho biết vị trí lắp m vòi nước tại m cây có số thứ tự là X₁, X₂, …, X_m (1 ≤ X₁ < X₂ < … < X_m ≤ n) và các bán kính tưới nước là R₁, R₂, …, R_m (1 ≤ Rᵢ ≤ 100).

Yêu cầu: Tính xem, có bao nhiêu cây được tưới nước khi lắp m vòi nước tự động như trên. Một cây được tưới nước nếu có ít nhất một vòi nước có thể tưới nước cho cây đó.

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

• Dòng 1 ghi hai số nguyên dương n và m (2 ≤ n ≤ 2000; 1 ≤ m ≤ n) tương ứng là số cây và số vòi nước.
• m dòng tiếp theo, dòng thứ i (i = 1, 2, …, m) ghi hai số nguyên Xᵢ, Rᵢ. Trong đó Xᵢ là số thứ tự của cây đặt vòi nước thứ i, Rᵢ là bán kính tưới nước.

Kết quả: ghi ra tệp văn bản HangCay.Out gồm một số nguyên duy nhất là số cây được tưới nước.

Ví dụ:

hangcay.inp	hangcay.out
8 2 2 2 5 1	6

Giải thích:

• Vòi nước 1 đặt tại cây thứ 2, có thể tưới nước cho các cây thứ: 1, 2, 3, 4.
• Vòi nước 2 đặt tại cây thứ 5, có thể tưới nước cho các cây thứ: 4, 5, 6.

Vậy có 6 cây được tưới nước.

Giới hạn:

• Có 30% số test ứng với 30% số điểm thỏa mãn 2 ≤ n ≤ 200; m = 1.
• Có 30% số test ứng với 30% số điểm thỏa mãn 2 ≤ n ≤ 200; 2 ≤ m ≤ n; không có hai vòi nước trở lên có thể cùng tưới nước cho 1 cây.
• Có 40% số test ứng với 40% số điểm thỏa mãn 200 < n ≤ 2000; 2 ≤ m ≤ n.

Bài 3. Trò chơi chọn bóng

Ngày thành lập Đoàn 26/3 sắp đến. Tuấn cùng nhóm bạn của mình được giao thiết kế một trò chơi trí tuệ dành cho các đoàn viên trong trường. Sau một thời gian tìm hiểu và nghiên cứu, nhóm của Tuấn đã xây dựng một trò chơi có nội dung như sau:

Một rổ bóng có n quả bóng. Các quả bóng được đánh số từ 1 đến n. Quả bóng thứ i có màu được mã hóa bởi một số nguyên dương cᵢ (1 ≤ cᵢ ≤ k), trong đó k là số màu khác nhau trong n quả bóng. Mỗi lần chơi, người chơi sẽ chọn hai quả bóng khác màu trong rổ bóng và đưa hai quả bóng này ra khỏi rổ. Người chơi sẽ dừng lại khi trong rổ không còn quả bóng nào hoặc không có hai quả bóng khác màu. Số bóng được lấy ra khỏi rổ là số điểm của người chơi.

Tuấn cùng nhóm bạn muốn biết người chơi có thể đạt được điểm lớn nhất là bao nhiêu? Bạn hãy lập trình để tìm kết quả này nhé.

Yêu cầu: Đưa ra số điểm lớn nhất mà người chơi có thể nhận được.

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

• Dòng 1 ghi hai số nguyên n và k (2 ≤ k ≤ n ≤ 2×10⁵) tương ứng là số quả bóng trong rổ và số màu khác nhau của n quả bóng.
• Dòng 2 ghi n số nguyên dương c₁, c₂, …, cₙ (1 ≤ cᵢ ≤ k) tương ứng là mã màu của n quả bóng.

Kết quả ghi ra tệp văn bản ChonBong.Out gồm một số nguyên duy nhất là số điểm lớn nhất mà người chơi có thể nhận được.

Ví dụ:

chonbong.inp	chonbong.out	Giải thích
6 2 1 2 2 1 1 1	4	- Lần 1: Chọn quả bóng thứ 1 và thứ 2 với mã màu tương ứng là 1 và 2. - Lần 2: Chọn quả bóng thứ 3 và thứ 4 với mã màu tương ứng là 2 và 1. - Trong rổ bóng lúc này còn 2 quả thứ 5, 6 đều có mã màu bằng 1. Trò chơi kết thúc và người chơi được 4 điểm. Đây là số điểm cao nhất mà người chơi có thể nhận được.
4 3 3 3 1 2	4	- Lần 1: Chọn quả bóng thứ 1 và thứ 3 với mã màu tương ứng là 3 và 1. - Lần 2: Chọn quả bóng thứ 2 và thứ 4 với mã màu tương ứng là 3 và 2. Trong rổ bóng lúc này không còn quả bóng nào. Trò chơi kết thúc và người chơi được 4 điểm. Đây là số điểm cao nhất mà người chơi có thể nhận được.

Giới hạn:

• Có 20% số test ứng với 20% số điểm thỏa mãn 2 ≤ n ≤ 2000; k = 2.
• Có 30% số test ứng với 30% số điểm thỏa mãn 3 ≤ n ≤ 2000; k = 3.
• Có 30% số test ứng với 30% số điểm thỏa mãn 4 ≤ n ≤ 2000; 3 < k ≤ n.
• Có 20% số test ứng với 20% số điểm thỏa mãn 2000 < n ≤ 2×10⁵; 3 < k ≤ n.

Bài 4. Mật độ xuất hiện cao

Trò chơi chọn bóng mà nhóm của Tuấn thiết kế được bạn bè và giáo viên trong trường đánh giá rất cao. Sau thành công này, Tuấn cùng nhóm bạn tập trung học tập để thi vào lớp chuyên tin của một trường chuyên danh giá trong tỉnh. Những bài tập mà Tuấn làm đều yêu cầu kỹ năng thiết kế thuật toán chuyên nghiệp. Một trong các bài tập mà bạn ấy đang xây dựng thuật toán có nội dung như sau:

Cho chuỗi kí tự S chỉ gồm các kí tự chữ cái latinh thường từ ‘a’, …, ‘z’. Một chuỗi con X (gồm các kí tự ở vị trí liên tiếp) của S được gọi là một chuỗi có mật độ xuất hiện cao nếu trong chuỗi X có một kí tự mà số lần xuất hiện của kí tự đó nhiều hơn số các kí tự còn lại trong chuỗi X.

Ví dụ: chuỗi S = “abbbabced”, chuỗi con X = “abbbabc” là một chuỗi có mật độ xuất hiện cao, vì có kí tự ‘b’ xuất hiện 4 lần, số các kí tự còn lại bằng 3. Nếu X = “abbbabce”, kí tự xuất hiện nhiều lần nhất 4 lần (kí tự ‘b’) và số kí tự còn lại là 4. Do vậy chuỗi X = “abbbabce” không phải là một chuỗi có mật độ xuất hiện cao.

Yêu cầu: Tìm một chuỗi con X (gồm các kí tự ở vị trí liên tiếp) của S là một chuỗi có mật độ xuất hiện cao và độ dài lớn nhất.

Tuấn cũng đã có thuật toán của mình, còn bạn thì sao? Hãy lập trình giải bài toán trên để đối chiếu kết quả nhé.

Dữ liệu cho trong file văn bản MatDo.Inp gồm một chuỗi kí tự S chỉ gồm các kí tự chữ cái latinh thường và có độ dài không lớn hơn 2×10⁵.

Kết quả ghi ra file văn bản MatDo.Out gồm một số nguyên duy nhất là độ dài của chuỗi X tìm được.

Ví dụ:

matdo.inp	matdo.out	Giải thích
abbbabced	7	Ta có thể chọn chuỗi X thỏa mãn là: X = “abbbabc” hoặc X = “bbbabce”.
ababab	5	Ta có thể chọn chuỗi X thỏa mãn là: X = “ababa” vì kí tự ‘a’ xuất hiện 3 lần, số các kí tự còn lại là 2; hoặc X = “babab” vì kí tự ‘b’ xuất hiện 3 lần, số các kí tự còn lại là 2.
abc	1	Ta có thể chọn chuỗi X thỏa mãn là: X = “a” vì kí tự ‘a’ xuất hiện 1 lần, số các kí tự còn lại là 0; hoặc X = “b”, X = “c” đều thỏa mãn.

Giới hạn:

• Có 30% số test ứng với 30% số điểm thỏa mãn: Chuỗi S chỉ gồm các kí tự thuộc tập 3 kí tự ‘a’, ‘b’, ‘c’ và độ dài chuỗi S không quá 2×10³.
• Có 30% số test ứng với 30% số điểm thỏa mãn: Chuỗi S chỉ gồm các kí tự chữ cái latinh thường và độ dài chuỗi S không quá 2×10³.
• Có 40% số test ứng với 40% số điểm thỏa mãn: Chuỗi S chỉ gồm các kí tự chữ cái latinh thường và độ dài chuỗi S không quá 2×10⁵.