HSG THCS Thanh Hóa 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH Năm học 2025 - 2026
Môn thi: Tin học - THCS
Thời gian làm bài: 150 phút, không kể thời gian phát đề
(Đề thi có 03 trang, gồm 04 câu)

---

Tổng quan bài thi

Câu	Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp kết quả ra
Câu 1	Số đặc biệt	CAU1.*	CAU1.INP	CAU1.OUT
Câu 2	Xâu kí tự	CAU2.*	CAU2.INP	CAU2.OUT
Câu 3	Dãy số	CAU3.*	CAU3.INP	CAU3.OUT
Câu 4	Qua sông	CAU4.*	CAU4.INP	CAU4.OUT

Dữ liệu vào là đúng đắn, không cần phải kiểm tra. Trong các tệp dữ liệu vào/ra, nếu dữ liệu trên cùng một dòng thì được cách nhau bởi ít nhất 1 dấu cách. Dấu (*) trong tên tệp chương trình biểu thị đuôi tệp tùy thuộc vào ngôn ngữ lập trình sử dụng là CPP hoặc PY.

Câu 1. Số đặc biệt (8.0 điểm)

Một số nguyên dương K được gọi là số đặc biệt nếu số K² − 1 chia hết cho 5.

Ví dụ: 4 là số đặc biệt vì 4² − 1 = 15 chia hết cho 5;

7 không phải là số đặc biệt vì 7² − 1 = 48 không chia hết cho 5.

Yêu cầu: Cho 2 số nguyên dương L, R (2 ≤ L ≤ R ≤ 10¹⁸); hãy đếm các số đặc biệt trên đoạn [L, R].

Dữ liệu: Vào từ tệp CAU1.INP gồm một dòng chứa hai số nguyên dương L, R.

Kết quả: Ghi ra tệp CAU1.OUT một số duy nhất là kết quả của bài toán.

Ví dụ:

CAU1.INP	CAU1.OUT
2 8	2

Ràng buộc:

• Có 80% số điểm có 2 ≤ L ≤ R ≤ 10⁶;
• 20% số điểm còn lại không có ràng buộc gì thêm.

Câu 2. Xâu kí tự (6.0 điểm)

Cho xâu kí tự S chỉ chứa các kí tự IN HOA trong bảng chữ cái tiếng Anh.

Yêu cầu: Tìm độ dài lớn nhất của xâu con liên tiếp không chứa một trong các kí tự ‘A’, ‘N’, ‘H’.

Dữ liệu: Vào từ tệp CAU2.INP gồm:

• Dòng đầu tiên ghi số nguyên dương T, là số lượng xâu (T ≤ 10);
• T dòng tiếp theo, mỗi dòng ghi một xâu có độ dài không quá 10⁵ kí tự.

Kết quả: Ghi ra tệp CAU2.OUT gồm T dòng, mỗi dòng một số nguyên là độ dài xâu con liên tiếp tìm được theo yêu cầu, nếu không có xâu con liên tiếp thỏa mãn thì ghi ra -1.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
3 ABRBCDAB LCKHABWCHTHUR ANHA	5 3 -1	Độ dài lớn nhất của các xâu con thỏa mãn tương ứng là: - xâu 1: 5 ký tự BRBCD. - xâu 2: 3 kí tự ‘LCK’ và ‘BWC’. - xâu 3: Không có xâu thỏa mãn.

Ràng buộc:

• Có 30% số điểm có xâu đầu vào chỉ có một kí tự ‘A’ và không có ‘N’, ‘H’;
• Có 30% số điểm có xâu đầu vào có một kí tự ‘A’, một kí tự ‘H’, không có kí tự ‘N’ và độ dài xâu ≤ 10²;
• 40% số điểm còn lại không có ràng buộc gì thêm.

Câu 3. Dãy số (4.0 điểm)

Cho dãy số nguyên dương a₁, a₂, …, aₙ. Mỗi thao tác bạn được phép chọn một phần tử bất kỳ trong dãy để tăng lên 1 đơn vị.

Yêu cầu: Thực hiện m thao tác để phần tử nhỏ nhất của dãy (sau khi thực hiện m thao tác) nhận giá trị lớn nhất.

Dữ liệu vào: Vào từ tệp CAU3.INP gồm:

• Dòng đầu tiên gồm hai số nguyên n và m (1 ≤ n ≤ 2.10⁵; 0 ≤ m ≤ 10⁹) lần lượt là số lượng phần tử của dãy và số thao tác thực hiện;
• Dòng thứ hai gồm n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹) là giá trị ban đầu của các phần tử.

Kết quả: Ghi ra tệp CAU3.OUT một số nguyên duy nhất là giá trị nhỏ nhất của dãy số sau khi thực hiện m thao tác theo yêu cầu trên.

Ví dụ:

CAU3.INP	CAU3.OUT
5 6 2 8 6 5 9	6

Ràng buộc:

• Có 20% số điểm có giá trị n ≤ 10⁵ và m ≤ 1;
• Có 20% số điểm có giá trị n = 2 và m ≤ 10²;
• Có 30% số điểm có giá trị n ≤ 10³ và m ≤ 10²;
• 30% số điểm còn lại không có ràng buộc gì thêm.

Câu 4. Qua sông (2.0 điểm)

Nhà của An cách trường học một con sông. Giữa dòng sông có N hòn đá nhô lên khỏi mặt nước được đánh số thứ tự từ 1 đến N theo hướng từ nhà đến trường. Mỗi lần đi học, An phải nhảy lên các hòn đá bắt đầu từ hòn đá thứ 1 đến hòn đá thứ N để lên bờ bên kia. Với mỗi bước nhảy, nếu đang đứng ở hòn đá thứ x, An có thể nhảy đến hòn đá thứ x + d, với d là ước nguyên dương của một trong K số nguyên dương a₁, a₂, …, a_K.

Một dãy các hòn đá mà An nhảy lên để đi từ hòn đá thứ 1 đến hòn đá thứ N gọi là một cách đi. Hai cách đi khác nhau nếu tồn tại một hòn đá An nhảy lên ở cách này nhưng không nhảy lên ở cách kia.

Yêu cầu: Hãy đếm số cách đi khác nhau mà An có thể thực hiện để đi từ hòn đá thứ 1 đến hòn đá thứ N.

Dữ liệu vào: Vào từ tệp CAU4.INP gồm:

• Dòng đầu tiên ghi hai số nguyên dương N, K;
• Dòng thứ hai gồm K số a₁, a₂, …, a_K (1 ≤ aᵢ ≤ 10⁶).

Kết quả ra: Ghi ra tệp CAU4.OUT một số duy nhất là số cách khác nhau mà An có thể thực hiện được khi chia lấy dư cho (10⁹ + 7).

Ví dụ:

CAU4.INP	CAU4.OUT	Giải thích
5 1 3	3	Có 3 cách là: 1 →(+1) 2 →(+1) 3 →(+1) 4 →(+1) 5 1 →(+1) 2 →(+3) 5 1 →(+3) 4 →(+1) 5

Ràng buộc:

• Có 40% số điểm có N ≤ 20; K = 1 và a₁ = 6;
• 60% số điểm còn lại có N ≤ 10⁵; K ≤ 10; aᵢ ≤ 10⁶ (với mọi i = 1..n).

---

Thí sinh không được sử dụng tài liệu. Giám thị coi thi không giải thích gì thêm.