HSG lớp 9 huyện Bảo Thắng (Lào Cai) 2023-2024

PHÒNG GIÁO DỤC VÀ ĐÀO TẠO HUYỆN BẢO THẮNG ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP HUYỆN Năm học 2023 - 2024
Môn thi: Tin học
Thời gian làm bài: 150 phút, không kể thời gian giao đề
(Đề thi gồm có 04 trang, 05 câu)

---

Ghi chú

Đây là đề thi học sinh giỏi cấp huyện (Phòng GD&ĐT huyện Bảo Thắng, tỉnh Lào Cai). Đề gốc không đặt tên cho từng câu; tên câu ở đây được đặt thêm để dễ tra cứu.

Tổng quan bài thi

Câu	Tên chương trình	File dữ liệu vào	File dữ liệu ra	Điểm
Câu 1	CAU01.*	CAU01.INP	CAU01.OUT	5.0
Câu 2	CAU02.*	CAU02.INP	CAU02.OUT	5.0
Câu 3	CAU03.*	CAU03.INP	CAU03.OUT	4.0
Câu 4	CAU04.*	CAU04.INP	CAU04.OUT	4.0
Câu 5	CAU05.*	CAU05.INP	CAU05.OUT	2.0

Lưu ý

• Dấu * trong phần tên chương trình tương ứng với ngôn ngữ lập trình mà thí sinh sử dụng, ví dụ PAS, CPP, Python…
• Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên.
• Thời gian chạy mỗi test không quá 0.2 giây (0.2s).

Câu 1. Cặp số anh em (5.0 điểm)

Số A được gọi là anh em với số B nếu tổng các ước của A bằng B hoặc tổng các ước của B bằng A. Chú ý ở đây ta quy định rằng cặp (A, B) và cặp (B, A) chỉ tính là một cặp, A khác B.

Nhập vào số tự nhiên N (N ≤ 3×10⁵). Đếm số cặp anh em trong đoạn [1, N].

Dữ liệu vào: Đọc từ tệp CAU01.INP gồm một dòng duy nhất chứa số tự nhiên N.

Dữ liệu ra: Ghi ra tệp CAU01.OUT gồm một dòng duy nhất chứa số cặp số anh em trong đoạn [1, N].

Ví dụ:

CAU01.INP	CAU01.OUT	Giải thích
10	5	Trong đoạn [1, 10] có 5 cặp số anh em là (2, 3); (3, 4); (4, 7); (5, 6); (7, 8)

Có 80% test có N ≤ 10⁴; Có 20% test có 10⁵ ≤ N ≤ 3×10⁵.

Câu 2. Đếm số nguyên tố (5.0 điểm)

Nhập vào 2 số tự nhiên A, B. Hãy đếm xem trong đoạn [A, B] có bao nhiêu số nguyên tố?

Dữ liệu vào: Đọc từ tệp CAU02.INP gồm một dòng duy nhất chứa 2 số tự nhiên A, B cách nhau bởi một khoảng trắng, A ≤ B ≤ 10⁷;

Dữ liệu ra: Ghi ra tệp CAU02.OUT gồm một dòng duy nhất chứa số lượng số nguyên tố trong đoạn [A, B].

Ví dụ:

CAU02.INP	CAU02.OUT	Giải thích
1 10	4	Có bốn số nguyên tố trong đoạn [1, 10] là: 2, 3, 5, 7

Có 80% test có 1 ≤ A ≤ B ≤ 10⁵; Có 20% test có 10⁶ ≤ A ≤ B ≤ 10⁷.

Câu 3. Chiến binh (4.0 điểm)

Trong một trò chơi chiến tranh trên máy tính, quân đội của bạn và quân đội của đối phương đều có N chiến binh. Mỗi chiến binh đều được biết đến qua một số đo sức mạnh.

Quân đội của bạn có thể chiến thắng nếu mỗi chiến binh của bạn có thể tiêu diệt được ít nhất một chiến binh của đối phương. Chiến binh A tiêu diệt được chiến binh B khi và chỉ khi số đo sức mạnh của A lớn hơn hẳn B.

Biết số đo sức mạnh cụ thể của các chiến binh của cả hai bên. Hãy cho biết đội quân của bạn có thể chiến thắng hay không.

Dữ liệu vào: Đọc từ tệp CAU03.INP gồm 3 dòng:

• Dòng thứ nhất chứa số nguyên N là số chiến binh trong mỗi đội quân.
• Dòng thứ hai chứa N số nguyên dương (a₁, a₂, a₃, …, aₙ) mô tả số đo sức mạnh của mỗi chiến binh trong đội quân của bạn.
• Dòng thứ ba chứa N số nguyên dương (b₁, b₂, b₃, …, bₙ) mô tả số đo sức mạnh của mỗi chiến binh trong đội quân của đối phương.

Ràng buộc:

• 0 < N ≤ 10⁵
• 1 ≤ aᵢ, bᵢ ≤ 10⁹, i = 1..N

Dữ liệu ra: Ghi ra tệp CAU03.OUT gồm một dòng duy nhất: Ghi ra chữ Yes nếu quân đội của bạn có thể chiến thắng theo mô tả của đề bài, ngược lại in ra chữ No.

CAU03.INP	CAU03.OUT	Giải thích
5 2 3 5 4 6 1 3 2 5 4	Yes	Quân đội của bạn có thể giành chiến thắng nên in ra chữ Yes
5 2 2 5 4 6 1 3 2 5 4	No	Quân đội của bạn không thể giành chiến thắng nên in ra chữ No

Câu 4. Xâu con đối xứng dài nhất (4.0 điểm)

Một xâu được gọi là đối xứng nếu nó không có ít hơn một kí tự và nếu ta đọc từ trái sang phải hay từ phải sang trái đều giống nhau.

Ví dụ: ‘A’, ‘TET’, ‘CAOOAC’ là các xâu đối xứng, còn ‘ABC’, ‘CAGHYD’ là các xâu không đối xứng.

Cho xâu kí tự S, có chiều dài N (1 ≤ N ≤ 1000). Hãy tìm chiều dài xâu con đối xứng dài nhất của S. Xâu con của xâu S là dãy các kí tự liên tiếp nhau trong S.

Dữ liệu vào: Đọc từ tệp CAU04.INP gồm hai dòng:

• Dòng đầu ghi giá trị N là độ dài của xâu S.
• Dòng thứ hai gồm N kí tự liên tiếp, các kí tự chỉ gồm các chữ cái tiếng Anh in hoa.

Dữ liệu ra: Ghi ra tệp CAU04.OUT gồm một dòng duy nhất chứa độ dài xâu con đối xứng dài nhất.

Ví dụ:

CAU04.INP	CAU04.OUT	Giải thích
18 IKACOBEGIGEBOCAHTM	13	Độ dài xâu con đối xứng dài nhất là 13
19 IKACOBEGIGEMHBEGIGE	5	Độ dài xâu con đối xứng dài nhất là 5

Câu 5. Đoạn có tổng lớn nhất (2.0 điểm)

Tranh thủ trong giờ ra chơi, hai bạn Nam và Bình rủ nhau chơi trò tìm số. Hai bạn lần lượt mỗi người viết một số nguyên lên bảng, cứ như vậy hai bạn viết được một dãy gồm N số a₁, a₂, …, a_N. Đến đây hai bạn chưa kịp chơi trò chơi của mình thì đã đến giờ học. Thầy vào lớp, sẵn thấy dãy số trên bảng, thầy đã đặt ra câu đố: Tìm một đoạn liên tiếp các số trong dãy số trên sao cho tổng giá trị các số trong đoạn đó là lớn nhất. Vì dãy số có quá nhiều số nên cả lớp nhìn hoa cả mắt mà vẫn chưa tìm ra được đáp án. Em hãy lập trình giải giúp các bạn trong lớp nhé.

Dữ liệu vào: Đọc từ tệp CAU05.INP có dạng như sau:

• Dòng đầu tiên ghi số nguyên N (1 ≤ N ≤ 10⁵)
• Dòng thứ hai ghi dãy số nguyên a₁, a₂, …, a_N (|aᵢ| ≤ 1000, i = 1..N)

Dữ liệu ra: Ghi ra tệp CAU05.OUT gồm một số nguyên duy nhất là tổng lớn nhất của một đoạn liên tiếp các số trong dãy.

Ví dụ:

CAU05.INP	CAU05.OUT	Giải thích
10 2 -9 4 1 -3 5 8 -7 3 1	15	Chọn các phần tử: 4, 1, −3, 5, 8

Có 30% test có N ≤ 400; Có 30% test có 10³ < N ≤ 10⁴; Có 40% test có 10⁵ < N ≤ 10⁶.

---

Lưu ý:

• Thí sinh chỉ được sử dụng máy vi tính không có kết nối mạng khi làm bài.
• Giám thị không giải thích gì thêm.