Chọn đội tuyển HSG quốc gia Đồng Nai 2026-2027

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

KỲ THI LẬP ĐỘI TUYỂN HỌC SINH GIỎI DỰ THI CẤP QUỐC GIA THPT Năm học 2026 - 2027
Môn thi: Tin học
Thời gian: 180 phút mỗi ngày (không kể thời gian giao đề)
Ngày thi thứ nhất: 27/8/2026 - Ngày thi thứ hai: 28/8/2026

---

Ngày thi thứ nhất

Tổng quan đề thi

Bài	Tên bài	Tệp chương trình	Tệp vào	Tệp ra	Điểm
1	Lễ hội ánh sáng	BAI1.*	BAI1.INP	BAI1.OUT	7
2	Ổ khóa số	BAI2.*	BAI2.INP	BAI2.OUT	7
3	Mạng lưới giao thông	BAI3.*	BAI3.INP	BAI3.OUT	6

(* có thể là cpp hoặc py tùy theo thí sinh sử dụng ngôn ngữ lập trình C++ hay Python)

Bài 1. Lễ hội ánh sáng (7 điểm)

Trung tâm tổ chức sự kiện ABC đang chuẩn bị một lễ hội ánh sáng tại quảng trường trung tâm. Trên bản thiết kế có n cột đèn đã được lắp tại n vị trí phân biệt; mỗi vị trí được biểu diễn bởi một điểm có tọa độ nguyên (xᵢ, yᵢ) trên mặt phẳng. Ban tổ chức muốn toàn bộ hệ thống đèn có tâm đối xứng, nghĩa là tồn tại một điểm O sao cho với mỗi cột đèn tại vị trí A, vị trí đối xứng của A qua O cũng có một cột đèn. Điểm O có thể trùng với vị trí của một cột đèn đã có hoặc là một vị trí không có cột đèn. Các cột đèn đã lắp không thể di chuyển, nhưng có thể lắp thêm cột đèn tại những vị trí mới, tọa độ của các vị trí được bổ sung không bắt buộc phải là số nguyên mà có thể là số thực. Hãy xác định số cột đèn ít nhất cần lắp thêm để hệ thống đèn thu được có tâm đối xứng.

Dữ liệu: nhập từ tệp văn bản BAI1.INP

• Dòng đầu chứa số nguyên n (2 ≤ n ≤ 1000) là số cột đèn đã được lắp.
• n dòng tiếp theo, mỗi dòng chứa hai số nguyên xᵢ, yᵢ là tọa độ vị trí của cột đèn thứ i (−20000 ≤ xᵢ, yᵢ ≤ 20000).

Kết quả: ghi ra tệp văn bản BAI1.OUT

• Một số nguyên duy nhất là số cột đèn ít nhất cần lắp thêm.

Ví dụ:

BAI1.INP	BAI1.OUT	Giải thích
2 0 0 2 2	0	Hai điểm (0,0) và (2,2) có tâm đối xứng là điểm (1,1), do đó không cần thêm bất kỳ điểm nào để tạo thành tập hợp có tâm đối xứng.
6 0 0 4 0 0 4 4 4 1 1 1 2	2	Cần thêm vào 2 cột đèn tại các vị trí (3,2) và (3,3) để tập hợp có tâm đối xứng là điểm (2,2).

Ràng buộc:

• 40% test ứng với 40% số điểm có n ≤ 20.
• 30% test ứng với 30% số điểm có n ≤ 200.
• 30% test ứng với 30% số điểm không có ràng buộc gì thêm.

Bài 2. Ổ khóa số (7 điểm)

Nam có một ổ khóa số gồm n vòng số. Mỗi vòng số gồm các chữ số theo thứ tự từ 0 đến 9. Một cấu hình của ổ khóa được biểu diễn bởi một xâu gồm n chữ số, trong đó chữ số thứ i tương ứng với số đang hiển thị của vòng số i.

Ban đầu, ổ khóa ở cấu hình 00…0 (n chữ số 0). Mỗi giây, Nam có thể xoay một vòng số đúng 1 đơn vị theo một trong hai chiều:

• Xoay theo chiều xuôi sẽ tăng chữ số hiển thị lên 1 đơn vị. Nếu chữ số đang là 9 thì sau khi tăng sẽ trở thành 0.
• Xoay theo chiều ngược sẽ giảm chữ số hiển thị xuống 1 đơn vị. Nếu chữ số đang là 0 thì sau khi giảm sẽ trở thành 9.

Ví dụ:

• 3 → 4: xoay theo chiều xuôi mất 1 giây.
• 3 → 2: xoay theo chiều ngược mất 1 giây.
• 9 → 0: xoay theo chiều xuôi mất 1 giây.
• 0 → 9: xoay theo chiều ngược mất 1 giây.
• 2 → 8: xoay theo chiều ngược 2 → 1 → 0 → 9 → 8, mất 4 giây.
• 2 → 8: xoay theo chiều xuôi 2 → 3 → 4 → 5 → 6 → 7 → 8 lại mất 6 giây.

Nam được cho một danh sách gồm m cấu hình và phải xoay các vòng số để mỗi cấu hình xuất hiện ít nhất một lần. Các cấu hình có thể xuất hiện theo thứ tự bất kỳ, nhưng cấu hình xuất hiện cuối cùng phải là cấu hình thứ m trong danh sách.

Yêu cầu: Hãy xác định thời gian nhỏ nhất để thực hiện.

Dữ liệu: nhập từ tệp văn bản BAI2.INP

• Dòng đầu tiên chứa hai số nguyên n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 18).
• m dòng tiếp theo, mỗi dòng chứa một xâu gồm n chữ số biểu diễn một cấu hình. Các cấu hình đôi một khác nhau.

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

• Một số nguyên duy nhất là thời gian nhỏ nhất cần để thực hiện yêu cầu.

Ví dụ:

BAI2.INP	BAI2.OUT	Giải thích
4 3 1234 5678 9012	38	Ta xoay các vòng khóa để hiện các cấu hình theo thứ tự: 0000 → 5678 → 1234 → 9012. Thời gian xoay từ 0000 đến 5678: 5 + 4 + 3 + 2 = 14 Thời gian xoay từ 5678 đến 1234: 4 + 4 + 4 + 4 = 16 Thời gian xoay từ 1234 đến 9012: 2 + 2 + 2 + 2 = 8 Tổng thời gian là 38. Đây là cách xoay có thời gian ít nhất.

Ràng buộc:

• 10% test ứng với 10% số điểm có m = 3.
• 30% test ứng với 30% số điểm có m ≤ 8.
• 60% test ứng với 60% số điểm không có ràng buộc gì thêm.

Bài 3. Mạng lưới giao thông (6 điểm)

Thành phố XYZ đang xây dựng hệ thống số phục vụ công tác quản lý và đánh giá khả năng kết nối của mạng lưới giao thông đô thị. Trong hệ thống này có n nút giao thông quan trọng, được đánh số từ 1 đến n và n tuyến đường hai chiều. Mỗi tuyến đường kết nối trực tiếp giữa hai nút giao thông khác nhau, giữa hai nút giao thông có tối đa một tuyến đường kết nối trực tiếp. Mạng lưới được quy hoạch sao cho từ một nút giao thông bất kỳ đều có thể di chuyển đến mọi nút giao thông khác thông qua một hoặc nhiều tuyến đường.

Để xây dựng phương án ứng phó khi xảy ra sự cố lớn, thành phố cần đánh giá mức độ quan trọng của từng tuyến đường. Trong một tình huống đặc biệt, nếu nút giao thông u phải tạm ngừng hoạt động, thì tất cả các tuyến đường kết nối với nút này cũng không thể sử dụng. Một tuyến đường (u, v) được gọi là trọng yếu nếu hai nút giao thông u và v tạm ngừng hoạt động thì mạng lưới giao thông còn lại bị chia thành ít nhất hai khu vực không thể di chuyển tới nhau.

Yêu cầu: Hãy cho biết thành phố XYZ có bao nhiêu tuyến đường trọng yếu?

Dữ liệu: nhập từ tệp văn bản BAI3.INP

• Dòng đầu gồm số nguyên n (4 ≤ n ≤ 10⁵) là số nút giao thông và số tuyến đường kết nối trực tiếp.
• Trong n dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v (1 ≤ u, v ≤ n, u ≠ v) cho biết có một tuyến đường kết nối trực tiếp giữa hai nút giao thông u và v.

Kết quả: ghi ra tệp văn bản BAI3.OUT

• Một số nguyên duy nhất là số tuyến đường trọng yếu.

Ví dụ:

BAI3.INP	BAI3.OUT	Giải thích
4 1 2 1 3 1 4 2 3	2	Các tuyến đường nối nút (1) và (2); nối nút (1) và (3) là tuyến kết nối trọng yếu. Nếu hai nút (1) và (2) đồng thời ngừng hoạt động, mạng lưới chỉ còn lại nút (3) và nút (4). Hai nút này không có đường đi đến nhau, vì vậy mạng lưới còn lại bị mất kết nối. Nếu hai nút (1) và (3) đồng thời ngừng hoạt động, mạng lưới chỉ còn lại nút (2) và nút (4). Hai nút này không có đường đi đến nhau, vì vậy mạng lưới còn lại bị mất kết nối. Các tuyến đường khác không có tính chất này. Do đó, đáp án là 2.

Ràng buộc:

• 10% số test ứng với 10% số điểm có n ≤ 100.
• 30% số test ứng với 30% số điểm có n ≤ 1000.
• 60% số test ứng với 60% số điểm không có ràng buộc gì thêm.

Ngày thi thứ hai

Tổng quan đề thi

Bài	Tên bài	Tệp chương trình	Tệp vào	Tệp ra	Điểm
4	Xếp hàng	BAI4.*	BAI4.INP	BAI4.OUT	7
5	Xâu ngoặc đúng	BAI5.*	BAI5.INP	BAI5.OUT	7
6	Thu thập mẫu vật	BAI6.*	BAI6.INP	BAI6.OUT	6

(* có thể là cpp hoặc py tùy theo thí sinh sử dụng ngôn ngữ lập trình C++ hay Python)

Bài 4. Xếp hàng (7 điểm)

Nhân dịp lễ khai giảng năm học 2026-2027, trường THPT XYZ lên kế hoạch tổ chức cho học sinh đón chào đại biểu tham dự lễ.

Hiện tại thầy phụ trách đang sắp xếp n học sinh đứng thành một hàng ngang từ trái sang phải, học sinh thứ i mặc áo màu aᵢ. Để hàng học sinh được đẹp mắt, thầy phụ trách cần điều chỉnh sao cho dãy màu áo của các học sinh tạo thành một dãy đối xứng. Một dãy được gọi là đối xứng nếu giống nhau khi đọc từ trái sang phải và từ phải sang trái. Ví dụ: dãy 1 2 2 1 là một dãy đối xứng trong khi dãy 1 2 3 1 thì không.

Để điều chỉnh, thầy phụ trách có thể thực hiện một số thao tác, mỗi thao tác sẽ thực hiện một trong hai công việc:

• Loại một học sinh bất kỳ ra khỏi hàng.
• Đổi màu áo của một học sinh bất kỳ trong hàng sang một màu khác.

Yêu cầu: Hãy giúp thầy phụ trách thực hiện ít thao tác nhất để dãy màu áo của các học sinh trong hàng trở thành dãy đối xứng, trong các phương án cùng thực hiện ít thao tác nhất, hãy đưa ra phương án sao cho độ dài dãy đối xứng là dài nhất.

Dữ liệu: nhập từ tệp văn bản BAI4.INP

• Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 3000).
• Dòng tiếp theo chứa n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 3000) là số biểu thị màu áo của học sinh.

Kết quả: ghi ra tệp văn bản BAI4.OUT

• Dòng đầu ghi số nguyên x là số thao tác ít nhất cần thực hiện.
• Dòng thứ hai ghi số nguyên y là độ dài lớn nhất của dãy đối xứng tìm được khi thực hiện x thao tác.

Ví dụ:

BAI4.INP	BAI4.OUT	Giải thích
7 5 4 3 3 1 5 2	2 6	Một phương án tối ưu là: Đổi màu áo của học sinh thứ 2 thành màu 1, sau đó loại học sinh thứ 7 ra khỏi hàng. Lúc này màu áo của các học sinh trong hàng lần lượt là 5 1 3 3 1 5, đây là dãy đối xứng cần tìm.

Ràng buộc:

• 30% test ứng với 30% số điểm có n ≤ 10.
• 30% test ứng với 30% số điểm có n ≤ 300.
• 40% test ứng với 40% số điểm không có ràng buộc gì thêm.

Bài 5. Xâu ngoặc đúng (7 điểm)

Cho số nguyên dương n và xâu S có 2n kí tự, được đánh số từ 1 đến 2n, mỗi kí tự là dấu ngoặc mở ’(’ hoặc dấu ngoặc đóng ’)’. Các kí tự trong xâu được chia thành n cặp, hai kí tự thuộc cùng một cặp không nhất thiết phải liên tiếp. Mỗi cặp cần xóa đi 1 kí tự sao cho n kí tự còn lại tạo thành xâu ngoặc đúng.

Xâu ngoặc đúng được định nghĩa như sau:

• Xâu rỗng là một xâu ngoặc đúng.
• Nếu A là một xâu ngoặc đúng thì (A) cũng là một xâu ngoặc đúng.
• Nếu A và B là các xâu ngoặc đúng thì AB cũng là một xâu ngoặc đúng.

Yêu cầu: Hãy xác định xem có cách xóa sao cho xâu gồm n kí tự còn lại tạo thành xâu ngoặc đúng không?

Dữ liệu: nhập từ tệp văn bản BAI5.INP

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 10⁵) là số bộ dữ liệu, mỗi bộ dữ liệu gồm:
  • Dòng đầu chứa số nguyên n (1 ≤ n ≤ 10⁵).
  • Dòng thứ hai chứa xâu S có 2n kí tự.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên aᵢ và bᵢ (1 ≤ aᵢ < bᵢ ≤ 2n) cho biết vị trí hai kí tự thuộc cặp thứ i. Các giá trị a₁, b₁, a₂, b₂, …, aₙ, bₙ đôi một khác nhau.

Tổng các giá trị của n trong t bộ dữ liệu không vượt quá 10⁵.

Kết quả: ghi ra tệp văn bản BAI5.OUT

• Gồm t dòng, mỗi dòng là câu trả lời tương ứng với một bộ dữ liệu. Nếu tồn tại cách xóa để tạo thành xâu ngoặc đúng thì in ra “Yes”, ngược lại in ra “No”.

Ví dụ:

BAI5.INP	BAI5.OUT	Giải thích
2 4 ))))(((( 2 7 5 8 1 6 3 4 4 (((()))) 1 3 2 7 5 6 4 8	No Yes	- Trong bộ dữ liệu đầu tiên: không có phương án xóa theo yêu cầu của đề bài để được xâu ngoặc đúng. - Trong bộ dữ liệu thứ hai: Ta có cách thực hiện như sau để tạo thành xâu ngoặc đúng: • Cặp (1, 3) xóa kí tự tại vị trí 3. • Cặp (2, 7) xóa kí tự tại vị trí 7. • Cặp (5, 6) xóa kí tự tại vị trí 6. • Cặp (4, 8) xóa kí tự tại vị trí 4. Sau khi xóa xong, n kí tự còn lại là (())

Ràng buộc:

• 10% test ứng với 10% số điểm có 1 ≤ n ≤ 10; t ≤ 10.
• 30% test ứng với 30% số điểm có 1 ≤ n ≤ 1000; t ≤ 1000.
• 60% test ứng với 60% số điểm không có ràng buộc gì thêm.

Bài 6. Thu thập mẫu vật (6 điểm)

Trong một chuyến thám hiểm Sao Hỏa, xe tự hành Atlas được giao nhiệm vụ khảo sát một vùng đồng bằng rộng lớn. Trên đồng bằng có N trạm khác nhau T₁, T₂, …, T_N và M địa điểm phân biệt P₁, P₂, …, P_M, mỗi địa điểm chứa một mẫu vật. Vị trí của các trạm và địa điểm chứa mẫu vật được biểu diễn bởi các tọa độ nguyên trên mặt phẳng.

Atlas di chuyển với vận tốc không đổi, để khảo sát vùng đồng bằng này, Atlas sẽ xuất phát từ trạm T₁ rồi lần lượt đi đến T₂, T₃, … và kết thúc tại T_N.

Hỗ trợ Atlas là robot trinh sát Nova, có nhiệm vụ thu thập các mẫu vật. Vận tốc di chuyển của Nova nhanh gấp hai lần vận tốc của Atlas. Nova xuất phát cùng lúc với Atlas tại trạm T₁, để hỗ trợ Atlas, Nova phải luôn xuất hiện cùng với Atlas lần lượt tại các trạm T₂, …, T_N và cũng kết thúc nhiệm vụ tại trạm T_N.

Khi Atlas đi từ trạm Tᵢ đến Tᵢ₊₁, Nova có thể đi cùng Atlas hoặc tách khỏi Atlas, di chuyển đến tối đa một địa điểm Pⱼ để lấy mẫu vật, sau đó di chuyển đến gặp Atlas tại Tᵢ₊₁. Để gặp Atlas tại trạm Tᵢ₊₁, Nova phải đến trước hoặc cùng lúc với Atlas. Do vận tốc di chuyển của Nova nhanh gấp hai lần vận tốc của Atlas, nên điều kiện để Nova đi từ trạm Tᵢ đến lấy mẫu vật tại điểm Pⱼ và đến gặp Atlas tại Tᵢ₊₁ là: d(Tᵢ, Pⱼ) + d(Pⱼ, Tᵢ₊₁) ≤ 2d(Tᵢ, Tᵢ₊₁), với d(A, B) là độ dài đoạn thẳng AB.

Yêu cầu: Hãy tìm số lượng mẫu vật nhiều nhất mà Nova có thể thu thập được.

Dữ liệu: nhập từ tệp văn bản BAI6.INP

• Dòng đầu chứa hai số nguyên N và M (2 ≤ N ≤ 100; 0 ≤ M ≤ 100).
• N dòng tiếp theo, dòng thứ i chứa hai số nguyên xᵢ, yᵢ là tọa độ vị trí của trạm Tᵢ (−1000 ≤ xᵢ, yᵢ ≤ 1000).
• M dòng tiếp, dòng thứ j chứa hai số nguyên uⱼ, vⱼ là tọa độ vị trí của điểm chứa mẫu vật thứ j (−1000 ≤ uⱼ, vⱼ ≤ 1000).

Kết quả: ghi ra tệp văn bản BAI6.OUT

• Một số nguyên duy nhất là số lượng mẫu vật nhiều nhất mà Nova có thể thu thập.

Ví dụ:

BAI6.INP	BAI6.OUT
4 3 0 0 3 0 1 1 5 2 3 3 2 -2 6 -2	2

Giải thích: Một cách đi để Nova lấy được nhiều mẫu vật nhất là: (0, 0) → (2, −2) → (3, 0) → (1, 1) → (3, 3) → (5, 2). Với cách đi này Nova lấy được 2 mẫu vật.

Ràng buộc:

• 10% test ứng với 10% số điểm có N, M ≤ 10.
• 30% test ứng với 30% số điểm có N, M ≤ 20.
• 60% test ứng với 60% số điểm 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.