HSG THPT Lâm Đồng 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO LÂM ĐỒNG ĐỀ THI CHÍNH THỨC
(Đề có 03 trang)

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

---

Tổng quan đề thi

Bài	Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp dữ liệu ra
Bài 1	Xâu con	XAUCON.*	XAUCON.INP	XAUCON.OUT
Bài 2	Cạm bẫy	CAMBAY.*	CAMBAY.INP	CAMBAY.OUT
Bài 3	Mật mã	MATMA.*	MATMA.INP	MATMA.OUT
Bài 4	Du lịch	DULICH.*	DULICH.INP	DULICH.OUT

Dấu * được thay thế bởi 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.

Bài 1. Xâu con (4 điểm)

Anny là một người rất đam mê khám phá, tình cờ Anny có được một tấm bản đồ kho báu. Trong hành trình tìm kiếm, Anny tìm được cửa kho báu thứ nhất, trên cửa có ghi một dãy ký tự tiếng Anh in thường liên tiếp nhau. Bản đồ kho báu cho biết mật mã để mở cửa lần này là số lượng xâu con đặc biệt của dãy ký tự trên.

Biết rằng, một xâu con đặc biệt là một dãy ký tự liên tiếp bắt đầu bằng một nguyên âm (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) và kết thúc bằng một phụ âm hoặc ngược lại.

Yêu cầu: Hãy giúp Anny đếm số lượng xâu con đặc biệt của xâu ký tự trên cửa.

Dữ liệu vào: Vào từ tập tin XAUCON.INP, gồm một dòng duy nhất chứa dãy ký tự theo đề bài.

Dữ liệu ra: Ghi vào tập tin XAUCON.OUT, gồm một số nguyên duy nhất là mật mã tìm được.

Ví dụ:

XAUCON.INP	XAUCON.OUT
abco	4

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có chiều dài xâu ≤ 10³;
• Có 50% số test ứng với 50% số điểm có chiều dài xâu ≤ 5×10⁵.

Bài 2. Cạm bẫy (6 điểm)

Sau khi mở được cửa thứ nhất của kho báu, Anny cần vượt qua một chướng ngại vật để mở cửa thứ hai. Chướng ngại vật lần này là một ma trận các số nguyên dương không vượt quá 10⁹ có chứa các cạm bẫy.

Bản đồ kho báu mô tả ma trận gồm N hàng và M cột. Cạm bẫy được đặt trên các hàng và các cột có chứa giá trị lớn nhất hoặc nhỏ nhất của ma trận.

Mật mã để mở cửa thứ hai của kho báu là số lượng ô của ma trận không chứa cạm bẫy.

Yêu cầu: Hãy giúp Anny đếm số ô của ma trận không chứa cạm bẫy.

Dữ liệu vào: Vào từ tập tin CAMBAY.INP, có cấu trúc như sau:

• Dòng đầu gồm hai số nguyên dương N và M được viết cách nhau một ký tự khoảng trắng;
• N dòng tiếp theo, mỗi dòng gồm M số nguyên, các số được viết cách nhau một ký tự khoảng trắng.

Dữ liệu ra: Ghi vào tập tin CAMBAY.OUT, gồm một số duy nhất là mật mã tìm được.

Ví dụ:

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

Ràng buộc:

• Có 40% số test ứng với 40% số điểm có: 1 ≤ N, M ≤ 10;
• Có 30% số test ứng với 30% số điểm có: 1 ≤ N, M ≤ 100;
• Có 30% số test ứng với 30% số điểm có: 1 ≤ N×M ≤ 5×10⁶.

Bài 3. Mật mã (6 điểm)

Sau khi qua cửa thứ hai, Anny gặp được cánh cửa thứ ba. Để mở cửa Anny cần có mật mã. Mật mã lần này là chữ số cuối cùng của phép toán aⁿ được ghi trên bản đồ kho báu.

Yêu cầu: Hãy giúp Anny tìm chữ số cuối cùng của phép toán aⁿ.

Dữ liệu vào: Vào từ tập tin MATMA.INP, gồm hai số nguyên dương a và n được viết cách nhau một ký tự khoảng trắng.

Dữ liệu ra: Ghi vào tập tin MATMA.OUT, gồm một số duy nhất là mật mã tìm được.

Ví dụ:

MATMA.INP	MATMA.OUT
2 5	2

Ràng buộc:

• Có 40% số test ứng với 40% số điểm có: 1 ≤ a ≤ 9; 1 ≤ n ≤ 10³;
• Có 30% số test ứng với 30% số điểm có: 1 ≤ a ≤ 10⁶; 1 ≤ n ≤ 10⁶;
• Có 30% số test ứng với 30% số điểm có: 1 ≤ a ≤ 10⁹; 1 ≤ n ≤ 10¹⁸.

Bài 4. Du lịch (4 điểm)

Sau khi tìm được kho báu, Anny sắp xếp một chuyến đi du lịch vòng quanh thế giới. Có N điểm du lịch Anny muốn ghé thăm, được đánh số từ 1 đến N. Giữa các điểm du lịch có các chuyến bay đi trực tiếp; chi phí để bay từ điểm i đến điểm j là Cᵢⱼ (có thể khác Cⱼᵢ) và 1 ≤ Cᵢⱼ ≤ 10⁹.

Anny muốn chọn một hành trình du lịch qua N điểm, mỗi điểm chỉ ghé thăm một lần duy nhất. Với tinh thần tiết kiệm, Anny muốn chọn một hành trình du lịch với tổng chi phí nhỏ nhất.

Yêu cầu: Hãy giúp Anny tìm được hành trình có tổng chi phí nhỏ nhất.

Dữ liệu vào: Vào từ tập tin DULICH.INP, có cấu trúc như sau:

• Dòng đầu ghi số nguyên dương N;
• Dòng thứ i trong N dòng tiếp theo, ghi N số nguyên không âm Cᵢⱼ là chi phí bay từ điểm i đến điểm j (1 ≤ j ≤ n).

Dữ liệu ra: Ghi vào tập tin DULICH.OUT, gồm một số nguyên dương duy nhất là tổng chi phí của hành trình nhỏ nhất tìm được.

Ví dụ:

DULICH.INP	DULICH.OUT
6 0 1 2 1 3 4 5 0 3 2 3 4 4 1 0 2 1 2 4 2 5 0 4 3 2 5 3 5 0 2 5 4 3 3 1 0	8

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có: 5 < n ≤ 10;
• Có 50% số test ứng với 50% số điểm có: 10 < n ≤ 15.

---

Hết