HSG lớp 9 Quảng Ngãi 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO QUẢNG NGÃI ĐỀ CHÍNH THỨC
(Đề thi có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 Năm học 2025 - 2026
Ngày thi: 27/3/2026 - Môn thi: Tin học
Thời gian làm bài: 150 phút

---

Tổng quan đề thi

Tên bài	File chương trình	File dữ liệu vào	File dữ liệu ra	Thời gian chạy tối đa
Bài 1	BAI1.*	BAI1.INP	BAI1.OUT	1 giây
Bài 2	BAI2.*	BAI2.INP	BAI2.OUT	1 giây
Bài 3	BAI3.*	BAI3.INP	BAI3.OUT	1 giây
Bài 4	BAI4.*	BAI4.INP	BAI4.OUT	1 giây

(Dấu * được thay thế bởi PY hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Python hoặc C++)

Lập trình giải các bài toán sau:

Bài 1 (5,0 điểm)

Cho số nguyên dương N (0 < N ≤ 2 × 10⁹).

Yêu cầu: Tính tổng bình phương các chữ số của N.

Dữ liệu vào: Từ tệp văn bản BAI1.INP gồm một số nguyên dương N.

Dữ liệu ra: Ghi ra tệp văn bản BAI1.OUT số nguyên duy nhất là kết quả tìm được.

Ví dụ:

BAI1.INP	BAI1.OUT
12	5

Bài 2 (5,0 điểm)

An muốn cắt sợi dây có chiều dài N mét thành ba đoạn dây có chiều dài mỗi đoạn là số nguyên dương (đơn vị mét) sao cho ba đoạn dây này là ba cạnh của một tam giác cân có cạnh đáy lớn hơn cạnh bên.

Tam giác cân là tam giác có hai cạnh bên bằng nhau, cạnh còn lại gọi là cạnh đáy.

Yêu cầu: Em hãy giúp An tính có bao nhiêu cách cắt sợi dây này.

Dữ liệu vào: Từ tệp văn bản BAI2.INP gồm một số nguyên dương N (0 < N ≤ 10¹⁶).

Dữ liệu ra: Ghi ra tệp văn bản BAI2.OUT số nguyên duy nhất là số cách cắt sợi dây theo yêu cầu. Nếu không thỏa mãn, in ra 0.

Ví dụ:

BAI2.INP	BAI2.OUT	Giải thích
25	2	Có 2 cách cắt sợi dây thành 3 đoạn thoả mãn theo đề là (7, 7, 11) và (8, 8, 9).

Lưu ý: Các cách cắt sợi dây thành ba đoạn chỉ chọn dạng (x mét, x mét, y mét).

Bài 3 (5,0 điểm)

Trong chuyến thám hiểm đến hành tinh Golden, nhóm bạn Nô-bi-ta vô tình khám phá một căn hầm bí mật, họ buộc phải nhập mật mã mới mở được cánh cửa. Trên cửa có khắc một đoạn mật mã S chỉ gồm hai loại ký tự là ‘A’ và ‘B’. Nô-bi-ta phát hiện thấy một phiến đá viết hướng dẫn cách duy nhất để mở cánh cửa, đó là phải tìm được độ dài của đoạn chữ cân bằng hoàn hảo dài nhất của S. Một đoạn chữ liên tiếp được đánh giá là cân bằng hoàn hảo nếu số lượng ký tự ‘A’ trong đoạn đó bằng chính xác số lượng ký tự ‘B’. Do đoạn mật mã rất dài nên các bạn giúp đỡ nhóm Nô-bi-ta hoàn thành nhiệm vụ trên.

Yêu cầu: Hãy tìm và in ra độ dài của đoạn chữ cân bằng hoàn hảo dài nhất trong đoạn mật mã S.

Dữ liệu vào: Từ tệp văn bản BAI3.INP gồm một xâu S (chỉ gồm hai loại ký tự ‘A’ và ‘B’). Độ dài của S không vượt quá 10⁶.

Dữ liệu ra: Ghi ra tệp văn bản BAI3.OUT số nguyên duy nhất là độ dài của đoạn chữ cân bằng hoàn hảo dài nhất tìm được. In ra 0 nếu S không có đoạn cân bằng hoàn hảo.

Ví dụ:

BAI3.INP	BAI3.OUT	Giải thích
AABABB	6	Xâu ‘AABABB’ có 3 ký tự ‘A’ và 3 ký tự ‘B’, nên đoạn chữ cân bằng hoàn hảo dài nhất là 6.
AAB	2	Đoạn chữ cân bằng hoàn hảo dài nhất là ‘AB’, có độ dài 2.

Ràng buộc:

• Subtask 1 (50% số điểm): Độ dài xâu S ≤ 10³.
• Subtask 2 (50% số điểm): Độ dài xâu S ≤ 10⁶.

Bài 4 (5,0 điểm)

Trong tựa game chiến thuật “Đế Chế Cổ Đại”, bạn đóng vai một vị tướng quân đang thiết lập một tuyến phòng thủ dọc theo biên giới. Trên tuyến đường biên giới thẳng tắp này, có sẵn N vị trí bằng phẳng khác nhau có thể dùng để xây dựng thành lũy. Tuy nhiên, tài nguyên hiện tại chỉ đủ để bạn xây dựng đúng K thành lũy (K < N), mỗi thành lũy được xây trên một vị trí. Giá trị khoảng cách giữa hai thành lũy gần nhau tương ứng với mức chênh lệch giá trị của hai vị trí đó.

Kẻ thù trong game sở hữu những cỗ máy bắn đá có khả năng sát thương diện rộng. Để giảm thiểu thiệt hại, tránh việc một lần bắn mà đá đập trúng nhiều thành lũy cùng lúc, bạn cần phải bố trí K thành lũy này sao cho khoảng cách gần nhất giữa hai thành lũy bất kỳ cần phải càng xa càng tốt.

Yêu cầu: Cho N vị trí trên bản đồ và K vị trí để xây thành lũy. Tìm giá trị X sao cho X là lớn nhất trong số các khoảng cách gần nhau nhất giữa hai thành lũy bất kỳ.

Dữ liệu vào: Đọc từ tệp văn bản BAI4.INP:

• Dòng đầu tiên chứa hai số nguyên dương N và K (2 ≤ K < N).
• Dòng thứ hai chứa N số nguyên dương A₁, A₂, …, A_N (0 ≤ Aᵢ ≤ 10⁹) là các vị trí cần xây dựng. Các vị trí này chưa sắp xếp.

Dữ liệu ra: Ghi ra tệp văn bản BAI4.OUT giá trị của X.

Ví dụ:

BAI4.INP	BAI4.OUT	Giải thích
5 3 1 2 8 4 9	3	Có thể chọn các vị trí để xây dựng, chẳng hạn: - Vị trí (2, 8, 4): Khoảng cách giữa hai thành lũy gần nhất là 2. - Vị trí (1, 8, 4): Khoảng cách giữa hai thành lũy gần nhất là 3. - Vị trí (8, 4, 9): Khoảng cách giữa hai thành lũy gần nhất là 1. … Vậy đáp án là 3.

Ràng buộc:

• Subtask 1 (40% số điểm): N ≤ 100.
• Subtask 2 (60% số điểm): N ≤ 10⁵.

---

Giám thị không giải thích gì thêm.