HSG lớp 12 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ó 4 trang)

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

---

Tổng quan đề thi

Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp kết quả	Thời gian
Bài 1	BAI1.*	BAI1.INP	BAI1.OUT	1 giây/test
Bài 2	BAI2.*	BAI2.INP	BAI2.OUT	1 giây/test
Bài 3	BAI3.*	BAI3.INP	BAI3.OUT	1 giây/test
Bài 4	BAI4.*	BAI4.INP	BAI4.OUT	1 giây/test

Dấu * là CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là C++ hoặc Python. Hãy lập trình giải các bài toán sau:

Bài 1 (4 điểm)

Cho dãy số gồm n số nguyên dương a₁, a₂, …, aₙ.

Yêu cầu: Với mỗi số nguyên aᵢ, hãy tìm hai số nguyên dương xᵢ, yᵢ (0 < xᵢ, yᵢ < aᵢ), sao cho xᵢ² − yᵢ² = aᵢ.

Dữ liệu vào từ tệp văn bản BAI1.INP có cấu trúc:

• Dòng 1: chứa số nguyên dương n (n ≤ 100);
• Dòng thứ 2: chứa n số nguyên dương a₁, a₂, …, aₙ (1 ≤ i ≤ n, aᵢ ≤ 10⁶). Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản BAI1.OUT có cấu trúc:

Ghi trên n dòng, dòng thứ i là đáp án của aᵢ, cụ thể:

• Nếu tồn tại bộ số xᵢ, yᵢ thoả yêu cầu thì ghi ra 2 số nguyên theo thứ tự xᵢ, yᵢ (Nếu tồn tại nhiều bộ số xᵢ, yᵢ thoả yêu cầu thì ghi ra bộ số có xᵢ nhỏ nhất);
• Ngược lại ghi ra -1.

Ví dụ:

BAI1.INP	BAI1.OUT
3 15 4 9	4 1 -1 5 4

Ràng buộc:

• Subtask 1: 50% số test (50% số điểm): aᵢ ≤ 10³;
• Subtask 2: 50% số test (50% số điểm): aᵢ ≤ 10⁶.

Bài 2 (6 điểm)

Thành phố Ánh Sáng đang triển khai một hệ thống đèn đường thông minh. Mỗi cột đèn được gán một mã số nguyên dương duy nhất, đánh số thứ tự từ 1 và tăng dần theo trục đường chính của thành phố. Theo thiết kế kỹ thuật:

• Chỉ những cột đèn có mã số là số nguyên tố mới được lắp đặt bộ điều khiển thông minh;
• Các cột còn lại là đèn thường.

Yêu cầu: Do quy mô thành phố rất lớn, mã số của cột đèn có thể lên tới hàng tỷ. Hệ thống quản lý yêu cầu bạn xử lý nhiều truy vấn, mỗi truy vấn cho biết:

• Có bao nhiêu cột đèn thông minh trong đoạn từ đèn thứ L đến đèn thứ R?

Dữ liệu vào từ tệp văn bản BAI2.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên T (1 ≤ T ≤ 10⁵) - số lượng truy vấn;
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên L, R (1 ≤ L ≤ R ≤ 2 × 10⁹, R − L ≤ 10⁶), được ghi cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản BAI2.OUT có cấu trúc:

• T dòng: tương ứng với mỗi truy vấn in ra một dòng, chứa số lượng cột đèn đường thông minh trong đoạn [L, R].

Ví dụ:

BAI2.INP	BAI2.OUT
3 1 10 10 20 100 120	4 4 5

Ràng buộc:

• Subtask 1: 30% số test (30% số điểm) có T ≤ 10²; L, R ≤ 10³;
• Subtask 2: 40% số test (40% số điểm) có T ≤ 10³; L, R ≤ 10⁶;
• Subtask 3: 30% số test (30% số điểm) có T ≤ 10⁵; L, R ≤ 2 × 10⁹.

Bài 3 (5 điểm)

Sau nhiều năm nghiên cứu về người ngoài hành tinh, người ta đã thu được một thông tin mã hoá gồm n đoạn mã, sau phân tích người ta tính được đoạn mã thứ i có giá trị aᵢ (1 ≤ i ≤ n). Các chuyên gia nghiên cứu đang cần tìm mật mã của đoạn thông tin trên. Mật mã gồm các đoạn mã liên tiếp mà giá trị của mỗi đoạn mã không vượt quá giá trị mẫu x cho trước và số lượng đoạn mã là nhiều nhất.

Yêu cầu: Có m chuyên gia, mỗi chuyên gia cần tìm mật mã với giá trị mẫu không quá xⱼ (1 ≤ j ≤ m). Hãy giúp m chuyên gia tìm ra mật mã theo giá trị mẫu riêng của họ?

Dữ liệu vào từ tệp văn bản BAI3.INP có cấu trúc:

• Dòng đầu gồm 2 số nguyên n và m (n, m ≤ 10⁵);
• Dòng thứ 2 gồm n số nguyên a₁, a₂, …, aₙ (|aᵢ| ≤ 10⁹);
• m dòng tiếp theo, mỗi dòng gồm một số nguyên xⱼ (|xⱼ| ≤ 10⁹).

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản BAI3.OUT có cấu trúc:

• Gồm m dòng, mỗi dòng ghi một số nguyên là độ dài của mật mã tương ứng theo yêu cầu.

Ví dụ:

BAI3.INP	BAI3.OUT	Giải thích
5 4 0 -1 2 4 6 -3 2 1 5	0 3 2 4	Không tìm ra mật mã nào mà tất cả các đoạn mã ≤ −3 Mật mã có 3 đoạn mã liên tiếp gồm: 0 −1 2 đều ≤ 2 Mật mã có 2 đoạn mã liên tiếp gồm: 0 −1 đều ≤ 1 Mật mã có 4 đoạn mã liên tiếp gồm: 0 −1 2 4 đều ≤ 5

Ràng buộc:

• Subtask 1: 60% số test (60% số điểm): n, m ≤ 10³;
• Subtask 2: 40% số test (40% số điểm): n, m ≤ 10⁵.

Bài 4 (5 điểm)

Cho số nguyên dương n và dãy số nguyên A = (a₁, a₂, …, aₙ).

Yêu cầu: Tìm một dãy con dài nhất gồm các phần tử liên tiếp của A thỏa mãn: Tồn tại một số nguyên d > 1, sao cho mọi phần tử trong dãy con đó đều chia hết cho d.

Dữ liệu vào từ tệp văn bản BAI4.INP có cấu trúc:

• Dòng 1 chứa số nguyên dương T (T ≤ 10⁴) là số test;
• T nhóm dòng tiếp theo, mỗi nhóm gồm 2 dòng mô tả một test:
  • Dòng 1 chứa số nguyên dương n ≤ 10⁶;
  • Dòng 2 chứa n số nguyên a₁, a₂, …, aₙ cách nhau bởi dấu cách (∀i: |aᵢ| ≤ 10⁶).

Kết quả ghi ra tệp văn bản BAI4.OUT có cấu trúc:

• T dòng, mỗi dòng tương ứng với mỗi test, ghi ra một số nguyên duy nhất trên một dòng là độ dài dãy con tìm được. Nếu không tồn tại dãy con thỏa mãn điều kiện thì in ra số 0.

Ví dụ:

BAI4.INP	BAI4.OUT	Giải thích
5 3 1 2 3 8 2 6 12 15 27 1 81 5 6 2 4 6 8 10 12 12 4 5 7 9 4 5 7 9 4 5 7 9 3 1 1 1	1 4 6 1 0	Test 1: dãy con tìm được chỉ có một phần tử có thể chọn {2} hoặc {3} Test 2: dãy con tìm được {6, 12, 15, 27} Test 3: dãy con tìm được chính là dãy A Test 4: dãy con tìm được chỉ có một phần tử. Test 5: không tìm được dãy con thỏa điều kiện yêu cầu.

Ràng buộc:

• Subtask 1: 40% số test (40% số điểm): T ≤ 100 và n ≤ 100;
• Subtask 2: 60% số test (60% số điểm): không có ràng buộc gì thêm.

---

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