Chọn đội tuyển HSG quốc gia Lâm Đồng 2025-2026

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

KỲ THI CHỌN HỌC SINH VÀO ĐỘI TUYỂN BỒI DƯỠNG HSG QG NĂM HỌC 2025 - 2026 Môn thi: Tin học
Thời gian làm bài: 180 phút
Ngày thi: 19/9/2025

---

Tổng quan bài thi

Câu	Tên bài	File chương trình	File dữ liệu	File kết quả	Điểm
1	Thay ký tự	KYTU.*	KYTU.INP	KYTU.OUT	7,0
2	Kinh doanh cà phê	KINHDOANH.*	KINHDOANH.INP	KINHDOANH.OUT	7,0
3	Tô màu trên lưới	TOMAU.*	TOMAU.INP	TOMAU.OUT	6,0

Dấu * được thay thế bởi CPP, PAS hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là C++, Pascal hoặc Python. Hãy lập trình giải các bài toán sau:

Câu 1. Thay ký tự (7,0 điểm)

Cho hai xâu ký tự a và b. Biết rằng xâu a chỉ chứa các chữ số 0 và 1, còn xâu b chỉ chứa các chữ cái in thường. Bạn cần tìm hai xâu ký tự p và q sao cho:

• p và q là hai xâu khác rỗng;
• p và q chỉ chứa các chữ cái in thường;
• p ≠ q;
• Nếu thay mọi chữ số 0 trong a bởi p và thay mọi chữ số 1 trong a bởi q thì ta được xâu b.

Yêu cầu: Hãy đếm số cách chọn ra hai xâu p và q thoả mãn các điều kiện trên.

Dữ liệu vào: Cho trong tệp tin văn bản KYTU.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên T là số bộ dữ liệu. Tiếp theo là các bộ dữ liệu, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:
  • Dòng thứ nhất chứa xâu a. Xâu này chỉ chứa các chữ số 0 và 1; và chắc chắn có ít nhất một chữ số 0 và ít nhất một chữ số 1.
  • Dòng thứ hai chứa xâu b. Xâu này chỉ chứa các chữ cái in thường.

Gọi:

• |a| là độ dài xâu a;
• |b| là độ dài xâu b;
• Σa là độ dài xâu a trong tất cả các bộ dữ liệu;
• Σb là độ dài xâu b trong tất cả các bộ dữ liệu;

Dữ liệu đảm bảo:

• 2 ≤ |a| ≤ 10⁵ và 1 ≤ |b| ≤ 10⁶;
• Σa ≤ 5.10⁵ và Σb ≤ 5.10⁶.

Kết quả: Ghi ra tệp tin văn bản KYTU.OUT với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên là số cách chọn hai xâu p và q thoả mãn các điều kiện trên.

Ví dụ:

KYTU.INP	KYTU.OUT	Giải thích
2 01 zzzzzz 001 cucucucute	4 2	Trong bộ dữ liệu thứ nhất, các cặp xâu (p, q) có thể chọn là: z và zzzzz; zz và zzzz; zzzz và zz; zzzzz và z. Trong bộ dữ liệu thứ 2, các cặp xâu (p, q) có thể chọn là: cu và cucute; cucu và te.

Ràng buộc:

• Có 18% số test với |a| ≤ 10¹, |b| ≤ 10² và Σa ≤ 5.10¹, Σb ≤ 5.10², tương ứng 18% số điểm;
• Có 24% số test với |a| ≤ 10², |b| ≤ 10³ và Σa ≤ 5.10², Σb ≤ 5.10³, tương ứng 24% số điểm;
• Có 32% số test với |a| ≤ 10³, |b| ≤ 10⁴ và Σa ≤ 5.10³, Σb ≤ 5.10⁴, tương ứng 32% số điểm;
• Có 26% số test với |a| ≤ 10⁵, |b| ≤ 10⁶ và Σa ≤ 5.10⁵, Σb ≤ 5.10⁶, tương ứng 26% số điểm.

Câu 2. Kinh doanh cà phê (7,0 điểm)

Tỉnh Alpha có n phường được đánh số từ 1 đến n. Có n − 1 con đường hai chiều, con đường thứ i nối liền hai phường u_i và v_i. Một đường đi từ s đến t là một dãy các phường s, v₁, v₂, …, v_k, t sao cho hai phường liên tiếp trong dãy đều được nối bởi một con đường nào đó và độ dài của đường đi là k + 1. Khoảng cách giữa hai phường u và v là độ dài của đường đi ngắn nhất từ u đến v. Dữ liệu vào đảm bảo giữa hai phường bất kỳ đều có đường đi đến nhau.

Tập đoàn kinh doanh cà phê AiLegend đã mở m chi nhánh, chi nhánh thứ i nằm ở phường p_i. Do nhu cầu uống cà phê tăng cao của giới trẻ hiện nay, CEO tập đoàn AiLegend quyết định mở thêm đúng một chi nhánh nữa (hiển nhiên là ở một phường nào đó chưa có chi nhánh).

CEO tập đoàn AiLegend mong muốn rằng khoảng cách lớn nhất từ một phường bất kỳ chưa có chi nhánh đến một phường đã có chi nhánh là nhỏ nhất. Nói cách khác, gọi d_u là khoảng cách nhỏ nhất từ phường chưa có chi nhánh u đến một phường đã có chi nhánh. Gọi s = max(d_u) với u = 1, 2, …, n. CEO mong muốn mở thêm một chi nhánh sao cho giá trị của s là nhỏ nhất.

Yêu cầu: Bạn hãy giúp CEO tập đoàn AiLegend giải bài toán trên?

Dữ liệu vào: Cho trong tệp tin văn bản KINHDOANH.INP có cấu trúc như sau:

• Dòng đầu tiên chứa hai số nguyên n và m, lần lượt là số phường của tỉnh Alpha và số chi nhánh của tập đoàn AiLegend (1 ≤ n ≤ 300000 và 0 ≤ m ≤ n − 1);
• Dòng thứ hai chứa m số nguyên p₁, p₂, …, p_m (1 ≤ p_i ≤ n), là các phường đã có chi nhánh;
• n − 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v (1 ≤ u, v ≤ n), là con đường hai chiều trực tiếp nối phường u và phường v.

Kết quả: Ghi ra tệp tin văn bản KINHDOANH.OUT gồm một dòng là giá trị nhỏ nhất của s sau khi tập đoàn AiLegend thêm một chi nhánh.

Ví dụ:

KINHDOANH.INP	KINHDOANH.OUT	Giải thích
7 1 5 1 3 1 5 1 7 3 4 7 2 7 6	2	Ở ví dụ này, chọn phường 1 để mở thêm chi nhánh.
7 2 5 4 1 3 1 5 1 7 3 4 7 2 7 6	1	Ở ví dụ này, chọn phường 7 để mở thêm chi nhánh.

Ràng buộc:

• Có 20% số test tương ứng 20% số điểm với 1 ≤ n ≤ 3000;
• Có 20% số test tương ứng 20% số điểm với 1 ≤ n ≤ 300000, m = 0;
• Có 30% số test tương ứng 30% số điểm với 1 ≤ n ≤ 300000, m ≤ 10;
• Có 30% số test tương ứng 30% số điểm còn lại không có ràng buộc gì thêm.

Câu 3. Tô màu trên lưới (6,0 điểm)

Cho một lưới ô vuông gồm r hàng và c cột. Bạn cần tô mỗi cạnh của lưới bởi một trong ba màu đỏ (nét liền), xanh lục (nét lượn sóng), xanh lam (nét đứt đậm) sao cho với mỗi hình vuông đơn vị, tính chất sau được thỏa mãn: Bốn cạnh của hình vuông được tô bởi đúng hai màu khác nhau và mỗi màu xuất hiện trên đúng hai cạnh.

Ví dụ: với r = 2 và c = 3, hình bên trái thể hiện một cách tô hợp lệ, nhưng hình bên phải thì không hợp lệ bởi ô vuông đơn vị góc trái trên có ba cạnh màu xanh lam.

Yêu cầu: Hãy đếm số cách tô màu hợp lệ cho lưới ô vuông này.

Dữ liệu vào: Cho trong tệp tin văn bản TOMAU.INP gồm một dòng duy nhất chứa 2 số nguyên r và c (1 ≤ r, c ≤ 10⁹).

Kết quả: Ghi ra tệp tin văn bản TOMAU.OUT một số nguyên duy nhất là phần dư của số cách tô màu hợp lệ khi chia cho 10⁹ + 7.

Ví dụ:

TOMAU.INP	TOMAU.OUT
1 1	18
1 2	108

Ràng buộc:

• Có 10% số test tương ứng 10% số điểm với r = 1 và c ≤ 5;
• Có 14% số test tương ứng với 14% số điểm với r = 1 và c ≤ 2²⁰;
• Có 16% số test tương ứng với 16% số điểm với r = 1;
• Có 22% số test tương ứng với 22% số điểm với r ≤ 4 và c ≤ 3000;
• Có 18% số test tương ứng với 18% số điểm với r ≤ 4;
• Có 20% số test tương ứng 20% số điểm còn lại không có ràng buộc gì thêm.

---

Hết