HSG lớp 12 Gia Lai 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH GIA LAI ĐỀ THI CHÍNH THỨC
(Mỗi ngày thi gồm 04 trang, 03 bài)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 12 Năm học 2025 - 2026
Môn thi: Tin học
Thời gian: 180 phút mỗi ngày (không kể thời gian phát đề)
Ngày thi thứ nhất: 18/10/2025 - Ngày thi thứ hai: 19/10/2025

---

Lưu ý (áp dụng cho cả hai ngày thi):

• Phần mở rộng tên tệp chương trình theo ngôn ngữ lập trình của thí sinh (.pas; .cpp; .py).
• Khi chấm thi có xét đến thời gian xử lý bài toán của chương trình nên thí sinh không sử dụng các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm.
• File input và output ở trong thư mục hiện hành, thí sinh không khai báo đường dẫn đến file input và output.
• 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.

Ngày thi thứ nhất

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	Doremon truyền năng lượng (6 điểm)	ENERGY.*	ENERGY.INP	ENERGY.OUT
2	Xây dựng tuyến đường giao thông (7 điểm)	TRAFFIC.*	TRAFFIC.INP	TRAFFIC.OUT
3	Vòng ngọc cổ (7 điểm)	PEARL.*	PEARL.INP	PEARL.OUT

Bài 1. DOREMON TRUYỀN NĂNG LƯỢNG (6 điểm)

Doremon đang du hành vũ trụ thì phát hiện có n trạm không gian, giả sử các trạm được đánh số từ 1 đến n. Trạm thứ i có khả năng tiếp nhận năng lượng tối đa là a[i] (đơn vị năng lượng).

Doremon có khả năng truyền năng lượng trong phạm vi hoạt động K (K ≥ 0). Doremon sẽ chỉ truyền được năng lượng giữa các trạm có thể chịu được mức năng lượng K (a[i] ≥ K).

Ban đầu, Doremon nạp năng lượng cho trạm 1. Một trạm sau khi nhận được năng lượng có thể truyền tiếp cho các trạm bên phải trong phạm vi K (tức là các trạm có chỉ số trong đoạn [i+1, i+K], nếu các trạm đó có thể nhận được năng lượng ở mức K).

Nhiệm vụ của bạn là giúp Doremon tìm ra giá trị nhỏ nhất của K sao cho năng lượng có thể truyền được từ trạm 1 đến trạm n.

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

• Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 10⁷).
• Dòng thứ hai gồm n số nguyên a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ n).

Dữ liệu vào đảm bảo luôn tồn tại ít nhất một giá trị K thoả mãn yêu cầu.

Kết quả ra: Ghi ra tệp văn bản ENERGY.OUT gồm:

• Một số nguyên dương duy nhất là giá trị nhỏ nhất của K sao cho năng lượng có thể truyền từ trạm 1 đến trạm n.

Ví dụ:

ENERGY.INP	ENERGY.OUT	Giải thích
9 9 8 8 0 0 8 0 0 9	3	- Với K = 3, chỉ những trạm có khả năng a[i] ≥ 3 mới được tham gia truyền năng lượng: {1, 2, 3, 6, 9}. - Năng lượng bắt đầu truyền ở trạm 1: Trạm 1 → trạm 3 → trạm 6 → trạm 9. - Cuối cùng, năng lượng đến được trạm 9 ⇒ K = 3 là giá trị nhỏ nhất thoả mãn.

Ràng buộc:

• Có 20% số điểm tương ứng với n ≤ 100.
• Có 20% số điểm tương ứng với n ≤ 1000.
• Có 20% số điểm tương ứng với n ≤ 10⁵.
• Có 20% số điểm tương ứng với n ≤ 10⁶.
• Có 20% số điểm còn lại không có ràng buộc gì thêm.

Bài 2. XÂY DỰNG TUYẾN ĐƯỜNG GIAO THÔNG (7 điểm)

Quốc gia Z có N thành phố được nối với nhau bởi M con đường hai chiều và K sân bay. Khi đi qua một con đường nối hai thành phố U và V (1 ≤ U, V ≤ N) bằng ô tô thì sẽ mất thời gian là C phút. Mỗi thành phố có tối đa một sân bay và bất cứ chuyến bay nào đều có thời gian di chuyển mất T phút.

Lãnh đạo quốc gia Z đưa ra Q yêu cầu để đẩy mạnh phát triển cơ sở hạ tầng. Yêu cầu sau chỉ được thực hiện khi yêu cầu trước đó đã hoàn thành. Mỗi yêu cầu của lãnh đạo có thể thực hiện một trong ba loại công việc sau:

• Loại 1: Xây dựng một con đường hai chiều mới giữa hai thành phố U và V (1 ≤ U, V ≤ N) sao cho mất C phút khi di chuyển bằng ô tô.
• Loại 2: Xây dựng một sân bay mới ở một thành phố X (1 ≤ X ≤ N).
• Loại 3: Tính (∑ᵢ₌₁ᴺ ∑ⱼ₌₁ᴺ f(i, j)) với f(i, j) là tổng thời gian tối thiểu để đi từ thành phố i đến thành phố j qua các con đường và chuyến bay (nếu không có cách đi hoặc i = j thì f(i, j) = 0).

Yêu cầu: Bạn hãy giúp lãnh đạo mô hình hóa các yêu cầu loại 1 và 2, cho biết kết quả của các yêu cầu loại 3 tương ứng.

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

• Dòng đầu tiên chứa năm số nguyên N, M, Q, K, T (1 ≤ N, Q ≤ 400; 0 ≤ K ≤ N; 1 ≤ M ≤ 10³; 1 ≤ T ≤ 10⁹).
• Dòng thứ hai gồm K số nguyên đôi một phân biệt Aᵢ (1 ≤ i ≤ K) cho biết các thành phố có sân bay (1 ≤ Aᵢ ≤ N).
• M dòng tiếp theo, mỗi dòng gồm ba số nguyên U, V, C cho biết có con đường nối hai thành phố U và V với thời gian di chuyển là C phút (1 ≤ U, V ≤ N; U ≠ V; 1 ≤ C ≤ 10⁹).
• Q dòng cuối cùng, mỗi dòng được viết theo một trong ba định dạng tương ứng với ba loại yêu cầu sau:
  • Loại 1: 1 X Y C, tức xây dựng một con đường mới nối hai thành phố X và Y với thời gian di chuyển bằng ô tô là C (1 ≤ X, Y ≤ N; X ≠ Y; 1 ≤ C ≤ 10⁹).
  • Loại 2: 2 X, tức xây dựng một sân bay mới tại thành phố X (1 ≤ X ≤ N). Dữ liệu đảm bảo X chưa có sân bay trước yêu cầu này.
  • Loại 3: 3, tính tổng thời gian tối thiểu.

Kết quả ra: Ghi ra tệp văn bản TRAFFIC.OUT gồm:

• Với mỗi yêu cầu loại 3, ghi một số nguyên trên một dòng là kết quả tương ứng.

Ví dụ:

TRAFFIC.INP	TRAFFIC.OUT	Giải thích
3 1 3 2 100 2 3 1 3 50 3 1 2 3 30 3	600 320	- Yêu cầu loại 3 thứ nhất: ∑∑f(i,j) = f(1,1) + f(1,2) + f(1,3) + f(2,1) + f(2,2) + f(2,3) + f(3,1) + f(3,2) + f(3,3) = 0 + (50+100) + 50 + (100+50) + 0 + 100 + 50 + 100 + 0 = 600 - Yêu cầu loại 3 thứ hai: ∑∑f(i,j) = 0 + (50+30) + 50 + (30+50) + 0 + 30 + 50 + 30 + 0 = 320

Ràng buộc:

• Có 10% số điểm tương ứng với N, Q ≤ 100; M ≤ 200; K = 0, không có yêu cầu loại 2.
• Có 20% số điểm tương ứng với N, Q ≤ 100.
• Có 30% số điểm tương ứng với K = 0 và không có yêu cầu loại 2.
• Có 40% số điểm còn lại không có ràng buộc gì thêm.

Bài 3. VÒNG NGỌC CỔ (7 điểm)

Trong quá trình khảo cổ, nhà nghiên cứu Henry đã phát hiện một chuỗi gồm N hạt ngọc được xâu lại thành một vòng tròn khép kín. Henry đã đánh số các viên ngọc liên tiếp từ 1 đến N, viên ngọc thứ i (1 ≤ i < N) nằm liền kề với viên ngọc thứ i+1, viên ngọc thứ N nằm liền kề với viên ngọc thứ

1. Viên ngọc thứ i mang giá trị là một số nguyên dương Aᵢ.

Để phục vụ cho quá trình nghiên cứu, Henry bắt buộc phải tách chuỗi ngọc này thành K đoạn liên tiếp nhau để phân tích. Chi phí để tách một đoạn liên tiếp các chuỗi ngọc được tính bằng bình phương tổng giá trị các viên ngọc nằm trong đoạn đó.

Cụ thể, nếu một đoạn ngọc có m viên ngọc với giá trị các viên ngọc lần lượt là A₁, A₂, A₃, …, Aₘ chi phí để tách đoạn này là: (A₁ + A₂ + … + Aₘ)².

Tổng chi phí của quá trình tách thành K đoạn chính là tổng chi phí của K đoạn ngọc được tạo thành. Nhiệm vụ của Henry là tìm cách cắt chuỗi ngọc sao cho tổng chi phí để cắt là nhỏ nhất.

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

• Dòng đầu tiên chứa hai số nguyên dương N, K (2 ≤ K ≤ N ≤ 1000) – N là số lượng viên ngọc của chuỗi ngọc, K là số đoạn ngọc cần tách.
• Dòng thứ hai chứa N số nguyên dương A₁, A₂, A₃, …, A_N (1 ≤ Aᵢ ≤ 10⁵) – giá trị của các viên ngọc.

Kết quả ra: Ghi ra tệp văn bản PEARL.OUT gồm:

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất để chia chuỗi ngọc thành K đoạn.

Ví dụ:

PEARL.INP	PEARL.OUT	Giải thích
6 2 2 6 5 2 1 4	202	Chia chuỗi ngọc với thứ tự các chỉ số như sau: - Chuỗi ngọc 1: (2,3) - Chuỗi ngọc 2: (4, 5, 6, 1) - Tổng chi phí: (6 + 5)² + (2 + 1 + 4 + 2)² = 202

Ràng buộc:

• Có 20% số điểm tương ứng với K = 2, 2 ≤ N ≤ 10³
• Có 20% số điểm tương ứng với 2 ≤ K ≤ N ≤ 20.
• Có 20% số điểm tương ứng với 2 ≤ K ≤ N ≤ 100.
• Có 20% số điểm tương ứng với 2 ≤ K ≤ N ≤ 250.
• Có 20% số điểm tương ứng với 2 ≤ K ≤ N ≤ 500.

Ngày thi thứ hai

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
4	Phần tử giữa (6 điểm)	MEDIAN.*	MEDIAN.INP	MEDIAN.OUT
5	Chuyển hàng (7 điểm)	TRANSPORT.*	TRANSPORT.INP	TRANSPORT.OUT
6	Robot và trò chơi thu kẹo (7 điểm)	CANDY.*	CANDY.INP	CANDY.OUT

Bài 4. PHẦN TỬ GIỮA (6 điểm)

Phần tử giữa là phần tử nằm giữa của một tập hợp các số sau khi đã sắp xếp theo thứ tự không giảm. Nói cách khác, phần tử giữa chia dãy số thành hai phần sao cho:

• Một nửa số phần tử nhỏ hơn hoặc bằng phần tử giữa.
• Một nửa số phần tử lớn hơn hoặc bằng phần tử giữa.

Để tìm phần tử giữa của một dãy hữu hạn các số, ta sắp xếp theo thứ tự không giảm tất cả các số rồi lấy phần tử nằm giữa dãy số đó.

Cho bảng số nguyên không âm kích thước m × n (m dòng, n cột) và hai số lẻ r, c. Hãy tìm bảng con kích thước r × c để phần tử giữa của các số trong bảng là nhỏ nhất.

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

• Dòng đầu chứa bốn số nguyên m, n, r, c (1 ≤ m, n ≤ 1000; 1 ≤ r ≤ m; 1 ≤ c ≤ n).
• m dòng tiếp theo, mỗi dòng chứa n số nguyên không âm mô tả bảng số (các số không vượt quá 10⁹).

Kết quả ra: Ghi ra tệp văn bản MEDIAN.OUT gồm:

• Một số là phần tử giữa nhỏ nhất tìm được.

Ví dụ:

MEDIAN.INP	MEDIAN.OUT	Giải thích
5 5 5 3 9 10 11 12 8 1 2 3 4 5 13 14 1 10 1 5 20 7 8 25 13 15 6 8 9	8	Bảng con kích thước 5 × 3 cần tìm là: 10 11 12 2 3 4 14 1 10 20 7 8 15 6 8

Ràng buộc:

• Có 40% số điểm tương ứng với m, n ≤ 100.
• Có 30% số điểm tương ứng với m, n ≤ 300.
• Có 30% số điểm tương ứng với m, n ≤ 1000.

Bài 5. CHUYỂN HÀNG (7 điểm)

Mỗi ngày, công ty ABC cần vận chuyển N thùng hàng được đánh số từ 1 đến N. Được biết, thùng hàng i nặng Wᵢ ki-lô-gam, và ∑ᵢ₌₁ᴺ Wᵢ không vượt quá 10⁶ ki-lô-gam. Hiện tại, ở công ty chỉ có hai chiếc xe chở hàng, vì tính chất của công việc, toàn bộ N thùng này cần được vận chuyển trong một lần. Cả hai xe đều đảm bảo tải trọng để chở N thùng hàng.

Để đảm bảo quy tắc về vận chuyển, công ty đã đưa ra M quy định với quy định thứ j yêu cầu thùng hàng Pⱼ và Qⱼ không được vận chuyển trên cùng một xe.

Yêu cầu: Hãy tính số cách khác nhau để chia các thùng hàng ra cho hai xe mà vẫn tuân thủ các quy định. Hai cách vận chuyển được gọi là khác nhau nếu tổng khối lượng vận chuyển của xe một và tổng khối lượng vận chuyển của xe hai khác nhau trong hai cách.

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

• Dòng đầu tiên chứa một số nguyên dương T - số trường hợp cần tính (1 ≤ T ≤ 10).
• T nhóm dòng tiếp theo, mỗi nhóm dòng tương ứng một trường hợp có cấu trúc như sau:
  • Dòng đầu tiên chứa hai số nguyên N, M (2 ≤ N ≤ 5 × 10⁴; 0 ≤ M ≤ 10⁵).
  • Dòng thứ hai chứa N số nguyên, số thứ i là giá trị của Wᵢ (Wᵢ ≥ 1; ∑ᵢ₌₁ᴺ Wᵢ ≤ 10⁶).
  • M dòng tiếp theo, dòng thứ j gồm hai số nguyên Pⱼ, Qⱼ (1 ≤ Pⱼ, Qⱼ ≤ N; Pⱼ ≠ Qⱼ)

Kết quả ra: Ghi ra tệp văn bản TRANSPORT.OUT gồm:

• T dòng, dòng thứ i chứa một số nguyên là kết quả của trường hợp thứ i.

Ví dụ:

TRANSPORT.INP	TRANSPORT.OUT	Giải thích
2 5 2 3 2 3 2 5 1 2 1 3 3 3 5 7 8 1 3 2 3 1 2	6 0	- Trường hợp 1: có 6 cách vận chuyển như sau (Xe 1 / Xe 2): 3 / 2 3 2 5 3 2 / 2 3 5 3 2 5 / 2 3 2 3 2 / 3 5 2 3 2 5 / 3 3 5 / 2 3 2 - Trường hợp 2: không có cách vận chuyển phù hợp.

Ràng buộc:

• Có 18% số điểm tương ứng với N ≤ 500; M ≤ 1.
• Có 16% số điểm tương ứng với N ≤ 20; M ≤ 40.
• Có 20% số điểm tương ứng với ∑ᵢ₌₁ᴺ Wᵢ ≤ 3 × 10³.
• Có 18% số điểm tương ứng với ∑ᵢ₌₁ᴺ Wᵢ ≤ 2 × 10⁵.
• Có 28% số điểm còn lại không có ràng buộc gì thêm.

Bài 6. ROBOT VÀ TRÒ CHƠI THU KẸO (7 điểm)

Nhóm các bạn học sinh giỏi môn Tin học của tỉnh Gia Lai đã tạo một trò chơi. Hệ thống trò chơi được thiết kế gồm một số con robot và N trạm được đánh số liên tiếp từ 1 tới N. Các trạm được kết nối bởi N−1 đường đi hai chiều, đảm bảo giữa hai trạm bất kì đều tồn tại đường đi. Mỗi robot mang một con số may mắn W và một số viên kẹo. Mỗi trạm được đặt một con số vui vẻ Lᵢ. Nếu robot mang số may mắn W đi qua trạm thứ i có số vui vẻ Lᵢ mà W > Lᵢ, robot sẽ phải bỏ vào hộp kẹo của trạm i một lượng kẹo là W − Lᵢ viên. Nếu robot đi qua có con số may mắn W không lớn hơn số vui vẻ Lᵢ, robot sẽ được đi qua trạm i mà không phải mất kẹo. Biết rằng, số viên kẹo mà mỗi robot mang theo luôn đảm bảo để tham gia trò chơi.

Có M robot chuẩn bị tham gia trò chơi. Robot thứ i di chuyển từ trạm xuất phát Sᵢ đến trạm đích Tᵢ với số may mắn là Wᵢ. Mỗi robot đều đi theo đường đi sao cho khoảng cách di chuyển (số con đường đi qua) phải ít nhất. Tất cả robot đều bị kiểm tra và thu kẹo (nếu có) tại tất cả các trạm nằm trên con đường đi qua, bao gồm trạm xuất phát và trạm đích.

Yêu cầu: Hãy thống kê tổng số kẹo mà mỗi trạm đã thu được sau khi M robot này hoàn thành trò chơi.

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

• Dòng đầu tiên chứa hai số nguyên dương N và M (1 ≤ N, M ≤ 3 × 10⁵) – số lượng trạm và số lượng robot.
• N − 1 dòng tiếp theo: Mỗi dòng chứa hai số nguyên dương uᵢ và vᵢ (1 ≤ uᵢ, vᵢ ≤ N), thể hiện có một đường đi trực tiếp giữa hai trạm này.
• Dòng tiếp theo chứa N số nguyên L₁, L₂, …, L_N (0 ≤ Lᵢ ≤ 10⁹) - số vui vẻ của mỗi trạm.
• M dòng cuối cùng: Mỗi dòng chứa ba số nguyên Sᵢ, Tᵢ và Wᵢ (1 ≤ Sᵢ, Tᵢ ≤ N, 1 ≤ Wᵢ ≤ 10⁹) - thông tin về robot (trạm xuất phát, trạm đích, số may mắn của robot i).

Kết quả ra: Ghi ra tệp văn bản CANDY.OUT gồm:

• Một dòng duy nhất chứa N số nguyên (các số cách nhau bởi dấu cách), số thứ i là tổng số kẹo mà trạm i đã thu được.

Ví dụ:

CANDY.INP	CANDY.OUT	Giải thích
3 2 1 2 1 3 4 2 6 1 2 5 2 3 9	6 10 3	Trạm 1: đường đi 1→2 thu 1; đường đi 2→1→3 thu 5. Trạm 2: đường đi 1→2 thu 3; đường đi 2→1→3 thu 7. Trạm 3: đường đi 2→1→3 thu 3.

Ràng buộc:

• Có 20% số điểm tương ứng với N, M ≤ 100.
• Có 20% số điểm tương ứng với uᵢ = (i+1)/2, vᵢ = i + 1 với i = 1 … N − 1.
• Có 20% số điểm tương ứng với mỗi trạm kết nối không quá 2 trạm khác.
• Có 20% số điểm tương ứng với Lᵢ = 0 với mọi 1 ≤ i ≤ N.
• Có 20% số điểm còn lại không có ràng buộc gì thêm.

---

• Thí sinh KHÔNG được sử dụng tài liệu;
• Giám thị KHÔNG giải thích gì thêm.