HSG THPT 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 - THPT
Thời gian làm bài: 150 phút, không kể thời gian phát đề
(Đề thi có 4 trang, gồm 5 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	Cặp số	CAU1.*	CAU1.INP	CAU1.OUT
Câu 2	Ô tô bay	CAU2.*	CAU2.INP	CAU2.OUT
Câu 3	Nguyên tố cùng nhau	CAU3.*	CAU3.INP	CAU3.OUT
Câu 4	Xâu con	CAU4.*	CAU4.INP	CAU4.OUT
Câu 5	Bó hoa	CAU5.*	CAU5.INP	CAU5.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.

Câu 1. Cặp số (6 điểm)

Cho 2 số nguyên dương L, R.

Yêu cầu: Đếm số cặp số nguyên (a, b) thoả mãn:

• L ≤ a < b ≤ R;
• b² − a² là một số nguyên tố.

Dữ liệu: Vào từ tệp CAU1.INP gồm 2 số nguyên dương L, R (L < R ≤ 2.10⁵).

Kết quả: Ghi ra tệp CAU1.OUT một số nguyên là số cặp số thoả mãn tìm được.

Ví dụ:

CAU1.INP	CAU1.OUT
5 13	5

Ràng buộc:

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

Câu 2. Ô tô bay (5 điểm)

Hãng ô tô BN đang trong giai đoạn thử nghiệm một mẫu ô tô bay đời mới. Trong quá trình vận hành, khi gặp một chướng ngại vật có độ cao h, chiếc xe phải “nâng” độ cao của nó lên mức l ≥ h để vượt qua. Tuy nhiên, việc bay càng cao so với chướng ngại vật sẽ càng tiêu tốn nhiều năng lượng, vì vậy hãng quy ước độ lãng phí khi ô tô bay ở độ cao l và vượt chướng ngại vật độ cao h là l − h.

Trong bài thử nghiệm, có n chướng ngại vật đánh số từ 1 đến n có độ cao lần lượt là h₁, h₂, …, hₙ được xếp liên tiếp từ trái sang phải theo thứ tự từ 1 đến n trên một đường thẳng. Ô tô cần bay từ bên trái chướng ngại vật 1 qua bên phải chướng ngại vật n. Do đây vẫn là phiên bản thử nghiệm nên trong suốt quá trình thử nghiệm, ô tô chỉ được phép nâng độ cao của nó lên tối đa một lần và không được hạ độ cao. Khi xuất phát, ô tô được nâng lên độ cao bất kỳ và lần nâng này không tính vào lần nâng trong quá trình thử nghiệm.

Yêu cầu: Tìm tổng độ lãng phí nhỏ nhất để ô tô hoàn thành bài thử nghiệm như mô tả trên.

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

• Dòng 1: Gồm 2 số nguyên n, k (−1 ≤ k ≤ 1, 1 ≤ n ≤ 10⁶), trong đó n là số chướng ngại vật, số k có ý nghĩa như sau:
  • Nếu k = 0: Ô tô không được nâng độ cao lần nào nhưng độ cao xuất phát ban đầu tuỳ ý.
  • Nếu k = −1: Ô tô được nâng độ cao tối đa một lần và xe phải xuất phát ở độ cao bằng h₁.
  • Nếu k = 1: Ô tô được nâng độ cao tối đa một lần và được chọn độ cao xuất phát ban đầu tuỳ ý.
• Dòng 2: Gồm n số nguyên h₁, h₂, … hₙ (0 ≤ hᵢ ≤ 10⁹ với mọi i = 1..n) là độ cao của các chướng ngại vật.

Kết quả: Ghi ra tệp CAU2.OUT một số nguyên là tổng độ lãng phí nhỏ nhất tìm được theo yêu cầu.

Ví dụ:

CAU2.INP	CAU2.OUT
5 0 7 9 2 5 8	14
6 -1 5 4 6 8 3 6	10
7 1 5 4 6 8 9 3 7	12

Giải thích ví dụ 3: Xe xuất phát với độ cao bằng 6 và giữ độ cao này bay qua các chướng ngại vật thứ 1, 2, 3. Khi gặp chướng ngại vật thứ 4 xe nâng độ cao lên bằng 9 rồi giữ độ cao này bay về đích.

Tổng độ lãng phí là: (6−5) + (6−4) + (6−6) + (9−8) + (9−9) + (9−3) + (9−7) = 12

Ràng buộc:

• Có 40% số điểm có: k = 0 và N ≤ 10⁶;
• Có 30% số điểm tiếp theo có: k = −1 và N ≤ 10⁶;
• 30% số điểm còn lại có: k = 1 và N ≤ 10⁴;

Câu 3. Nguyên tố cùng nhau (4 điểm)

Cho 2 dãy số nguyên dương A = a₁, a₂, …, aₙ và B = b₁, b₂, …, bₘ.

Yêu cầu: Đếm số các chỉ số i của dãy A sao cho aᵢ nguyên tố cùng nhau (ước chung lớn nhất bằng 1) với tất cả các số ở dãy B.

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

• Dòng thứ nhất chứa hai số nguyên dương n, m (n, m ≤ 10⁶);
• Dòng thứ hai chứa dãy số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁶ với mọi i = 1..n).
• Dòng thứ ba chứa dãy số nguyên dương b₁, b₂, …, bₘ (bᵢ ≤ 10⁶ với mọi i = 1..m).

Kết quả: Ghi ra tệp CAU3.OUT gồm một số nguyên là số các chỉ số i tìm được.

Ví dụ:

CAU3.INP	CAU3.OUT
3 2 6 7 25 4 6	2

Ràng buộc:

• Có 30% số điểm có: n, m ≤ 10³;
• Có 30% số điểm tiếp theo có: tất cả các số ở dãy A và dãy B đều là số nguyên tố.
• 40% số điểm còn lại không có ràng buộc gì thêm.

Câu 4. Xâu con (3 điểm)

Cho xâu kí tự S chỉ gồm các chữ cái tiếng Anh in hoa.

Yêu cầu: Tìm xâu con liên tiếp dài nhất xuất hiện ít nhất K lần trong S, hai lần xuất hiện là khác nhau nếu vị trí bắt đầu của xâu con là khác nhau.

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

• Dòng đầu ghi hai số nguyên dương N và K tương ứng là độ dài của xâu S và số lần xuất hiện ít nhất của xâu con cần tìm (N, K ≤ 10⁵).
• Dòng thứ hai ghi xâu kí tự S.

Kết quả: Ghi ra tệp CAU4.OUT một số nguyên là độ dài xâu con tìm được theo yêu cầu, nếu không tồn tại xâu con thì ghi -1.

Ví dụ:

CAU4.INP	CAU4.OUT
3 2 ABC	-1
7 2 AABCAABA	3

Ràng buộc:

• Có 40% số điểm có N ≤ 10²;
• Có 30% số điểm tiếp theo có N ≤ 10⁴;
• 30% số điểm còn lại không có ràng buộc gì thêm.

Câu 5. Bó hoa (2 điểm)

Có n bông hoa được đánh số từ 1 đến n, bông hoa thứ i có độ đẹp là một số nguyên không âm aᵢ (với mọi i = 1..n). Tất cả n bông hoa được xếp thành một hàng ngang theo thứ tự từ 1 đến n. Người ta cần chia n bông hoa thành k bó hoa sao cho mỗi bó hoa được ghép bởi một số bông hoa liên tiếp theo thứ tự đã xếp, mỗi bông hoa thuộc một và chỉ một bó.

Độ đẹp của một bó hoa là độ đẹp của bông hoa có giá trị nhỏ nhất trong bó hoa đó.

Yêu cầu: Tìm cách chia n bông hoa thành k bó như mô tả trên sao cho tổng độ đẹp của k bó hoa là lớn nhất.

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

• Dòng đầu chứa hai số nguyên dương n và k (1 ≤ k ≤ n ≤ 10⁵; n.k ≤ 5.10⁶).
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 10⁹ với mọi i = 1..n).

Kết quả: Ghi ra tệp CAU5.OUT là tổng độ đẹp lớn nhất của k bó hoa như yêu cầu.

Ví dụ:

CAU5.INP	CAU5.OUT
5 2 3 4 1 5 2	4

Ràng buộc:

• Có 30% số điểm tiếp theo có: k ≤ 2;
• Có 40% số điểm tiếp theo có: n ≤ 500;
• 30% số điểm còn lại không còn ràng buộc gì thêm.

---

Hết