HSG THPT Gia Lai 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH GIA LAI ĐỀ THI CHÍNH THỨC
(Đề thi có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT Năm học 2025 - 2026
Môn thi: Tin học - Ngày thi: 24/03/2026
Thời gian: 180 phút (không kể thời gian phát đề)

---

Tổng quan đề thi

Bài	Tên bài (điểm)	Tên tệp chương trình	Tên tệp dữ liệu vào	Tên tệp kết quả ra
1	Đếm dãy (5,0 điểm)	DEMDAY.*	DEMDAY.INP	DEMDAY.OUT
2	Xâu đối xứng (5,0 điểm)	CNTPAL.*	CNTPAL.INP	CNTPAL.OUT
3	Chọn quà (5,0 điểm)	CHONQUA.*	CHONQUA.INP	CHONQUA.OUT
4	Tải ứng dụng (5,0 điểm)	APP.*	APP.INP	APP.OUT

• Dấu * được thay thế bởi PAS, CPP hoặc PY tương ứng với ngôn ngữ lập trình Pascal, C++ hoặc Python.
• Thời gian chạy mỗi test của chương trình không quá 01 giây.
• Bộ nhớ cần dùng cho mỗi test của chương trình không quá 1024MB.

Hãy lập trình giải các bài sau:

Bài 1. Đếm dãy (5,0 điểm)

Trong lý thuyết số học, bên cạnh việc nghiên cứu từng số riêng lẻ, việc khảo sát cấu trúc số học của cả một dãy số cũng mang lại nhiều điều thú vị. Đặc biệt, mối liên hệ giữa các phần tử thông qua ước số chung lớn nhất phản ánh “mức độ liên kết” về mặt số học giữa chúng.

Một dãy số nguyên dương được gọi là liên kết nếu ước chung lớn nhất của dãy là 1 và mức độ liên kết chính là tổng của chúng. Chẳng hạn, dãy [1,1,1,1] là liên kết có mức độ 4, vì dãy có ước chung lớn nhất là 1 và tổng là 4.

Yêu cầu: Cho một số nguyên dương S, hãy đếm có bao nhiêu dãy có cùng mức độ liên kết là S.

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

• Dòng 1 chứa số nguyên dương t ≤ 100 là số test;
• t dòng tiếp theo, mỗi dòng chứa một số nguyên dương S ≤ 10⁹ ứng với một test.

Kết quả: Ghi ra tệp văn bản DEMDAY.OUT

Ứng với mỗi test, ghi ra một số nguyên duy nhất trên một dòng là số dư của kết quả tìm được khi chia cho 10⁹ + 7.

Ví dụ:

DEMDAY.INP	DEMDAY.OUT	Giải thích
3 4 5 1	6 15 1	Với test thứ nhất: S = 4, ta có 6 dãy liên kết với mức độ 4 gồm: [1,1,1,1]; [1,1,2]; [1,2,1]; [2,1,1]; [1,3]; [3,1].

Ràng buộc:

• Subtask 1: 60% số test với S ≤ 20.
• Subtask 2: 40% số test còn lại không có ràng buộc gì thêm.

Bài 2. Xâu đối xứng (5,0 điểm)

Một xâu được gọi là xâu đối xứng nếu đọc từ trái sang phải hay đọc từ phải sang trái đều như nhau. Cho một xâu S có độ dài N chỉ gồm các ký tự từ ‘a’ đến ‘z’ và Q truy vấn. Mỗi truy vấn cho 2 số nguyên L và R (1 ≤ L ≤ R ≤ N).

Yêu cầu: Trong mỗi truy vấn, đếm số lượng các cặp (X, Y) thỏa mãn:

• L ≤ X ≤ Y ≤ R
• Xâu con từ vị trí X đến Y của xâu S là xâu đối xứng.

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

• Dòng 1: Gồm xâu S có độ dài N, chỉ chứa các ký tự in thường (1 ≤ N ≤ 5000);
• Dòng 2: Gồm 1 số nguyên Q là số lượng truy vấn (1 ≤ Q ≤ 10⁶);
• Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên L và R (1 ≤ L ≤ R ≤ N).

Kết quả: Ghi ra tệp văn bản CNTPAL.OUT gồm Q dòng, mỗi dòng là số lượng xâu con tìm được tương ứng với mỗi truy vấn trong file dữ liệu vào.

Ví dụ:

CNTPAL.INP	CNTPAL.OUT	Giải thích
caaaba 5 1 1 1 4 2 3 4 6 4 5	1 7 3 4 2	Với xâu ban đầu S=“caaaba”: + Truy vấn 1 (L=1, R=1): tìm được 1 xâu con đối xứng là S[1]=“c”. + Trong truy vấn 2 (L=1, R=4): tìm được 7 xâu con đối xứng là S[1]=“c”, S[2]=“a”, S[3]=“a”, S[4]=“a”, S[2..3]=“aa”, S[3..4]=“aa”, S[2..4]=“aaa”.

Ràng buộc:

• Subtask 1: 20% số test có N, Q ≤ 100;
• Subtask 2: 40% số test có N, Q ≤ 300;
• Subtask 3: 20% số test có N, Q ≤ 2000;
• Subtask 4: 20% số test không có ràng buộc gì thêm.

Bài 3. Chọn quà (5,0 điểm)

Nhân dịp chào mừng 75 năm ngày thành lập Đoàn TNCS HCM, Đoàn trường đã chuẩn bị một trò chơi đặc biệt gọi là “TRÒ CHƠI CHỌN QUÀ”.

Ban tổ chức đã chuẩn bị sẵn m loại món quà, số lượng mỗi loại không hạn chế. Loại quà thứ i có 2 tham số tính điểm là aᵢ và bᵢ, nếu Chi đoàn chọn món quà loại i lần đầu thì điểm số được tính là aᵢ và nếu tiếp tục chọn loại quà đó thêm lần nữa thì điểm số được tăng lên là bᵢ. Tóm lại, nếu Chi đoàn nào chọn quà loại i với số lượng là k lần thì điểm số được tính là aᵢ + (k − 1) * bᵢ. Mỗi Chi đoàn được phép chọn đúng n món quà mà Ban tổ chức đã chuẩn bị.

Yêu cầu: Bạn là một thành viên của đội chơi, bạn hãy tính toán để Chi đoàn lớp bạn chọn n món quà từ m loại sao cho tổng điểm đạt được là lớn nhất.

Dữ liệu: Cho từ tệp văn bản CHONQUA.INP gồm nhiều dòng:

• Dòng thứ nhất chứa hai số nguyên n, m (1 ≤ n ≤ 10⁹, 1 ≤ m ≤ 10⁶) – số món quà được chọn và loại món quà mà Ban tổ chức chuẩn bị;
• Dòng thứ i trong m dòng sau chứa hai số nguyên aᵢ và bᵢ (0 ≤ aᵢ, bᵢ ≤ 10⁹) – thông tin để tính điểm của loại quà thứ i.

Kết quả: Ghi ra tệp văn bản CHONQUA.OUT gồm một số duy nhất là điểm số lớn nhất của Chi đoàn sau khi chọn n món quà.

Ví dụ:

CHONQUA.INP	CHONQUA.OUT	Giải thích
3 3 7 1 2 5 5 0	14	Chọn: 1 món quà loại 1; 2 món quà loại 2. Tổng điểm: 7+(2+5)=14.
5 3 5 2 4 2 3 1	16	Chọn: 2 món quà loại 1; 2 món quà loại 2; 1 món quà loại 3. Tổng điểm: (5+1*2)+(4+1*2)+3=16.

Ràng buộc:

• Subtask 1: 20% số test có n ≤ 10³, m ≤ 10⁴;
• Subtask 2: 30% số test có n, m ≤ 10⁶;
• Subtask 3: 50% số test không có ràng buộc gì thêm.

Bài 4. Tải ứng dụng (5,0 điểm)

Ngày nay, việc sử dụng các phần mềm ứng dụng (sau đây gọi chung là APP) đã trở nên rất phổ biến. Và người dùng có xu hướng sử dụng tiếp các APP khác có liên quan với APP vừa dùng.

Để hỗ trợ cho việc kinh doanh, một công ty chuyên cung cấp APP trực tuyến đã thực hiện việc đánh giá sản phẩm của mình như sau: có N APP được đánh số từ 1 đến N. Mỗi APP có số lượt tải được biểu diễn bởi một số nguyên Aᵢ. Có Q truy vấn thuộc hai loại được đặt ra cụ thể:

• Loại 1 (1 u v): Ghi nhận thông tin khách hàng đã tải APP loại u và cũng tải APP loại v hoặc ngược lại.
• Loại 2 (2 u c): Đếm xem có bao nhiêu APP có đúng số lượt đã tải là c và liên quan với u. Nghĩa là, khách hàng đã tải APP loại u hoặc tải APP khác nhưng cũng đã tải APP loại u.

Với mỗi truy vấn loại 2, hãy in ra kết quả tương ứng.

Yêu cầu: Bạn là nhân viên của Công ty, bạn hãy thực hiện Q truy vấn trên.

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

• Dòng đầu tiên gồm hai số nguyên dương N, Q (1 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 2.10⁵)
• Dòng thứ hai gồm N số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ N)
• q dòng tiếp theo, mỗi dòng là một trong hai truy vấn:
  • 1 u v (1 ≤ u, v ≤ N, u ≠ v).
  • 2 u c (1 ≤ u, c ≤ N).

Kết quả: Ghi ra tệp văn bản APP.OUT:

• Với mỗi truy vấn loại 2, in ra một số nguyên trên một dòng là kết quả tương ứng.

Ví dụ:

APP.INP	APP.OUT	Giải thích
5 7 2 4 2 3 2 1 1 2 2 1 2 1 3 5 2 2 1 1 1 3 2 3 2 2 4 3	1 0 3 1	Truy vấn 1: Ghi nhận thông tin khách hàng đã tải APP loại 1 và cũng tải APP loại 2. Truy vấn 2: Có 1 APP được tải 2 lần đó là APP loại 1, đó là APP mang số hiệu 1. Truy vấn 3: Ghi nhận thông tin khách hàng đã tải APP loại 3 và cũng tải APP loại 5. Truy vấn 4: Có 0 APP được tải 1 lần thuộc loại 2 hoặc liên quan đến APP loại 2. Truy vấn 5: Ghi nhận thông tin khách hàng đã tải APP loại 3 và cũng tải APP loại 2. Truy vấn 6: Có 3 APP được tải 2 lần thuộc loại 2 hoặc liên quan đến APP loại 2, đó là APP mang số hiệu 3, 1, 5. Truy vấn 7: Có 1 APP được tải 3 lần thuộc loại 4 hoặc liên quan đến APP loại 4, đó là APP mang số hiệu 4.

Ràng buộc:

• Subtask 1: 30% số test có N, Q ≤ 1000
• Subtask 2: 30% số test có aᵢ = 1 với i = 1…N
• Subtask 3: 40% số test không có ràng buộc gì thêm.

---

Hết