Chọn đội tuyển HSG quốc gia Bắc Ninh 2025-2026

UBND TỈNH BẮC NINH SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỀ CHÍNH THỨC
(Ngày 1: 03 trang, ngày 2: 05 trang)

ĐỀ THI LẬP ĐỘI TUYỂN THAM DỰ KỲ THI CHỌN HỌC SINH GIỎI CẤP QUỐC GIA THPT NĂM HỌC 2025-2026 Môn thi: Tin học
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
Ngày thi: 11 và 12 tháng 9 năm 2025

---

Ngày thi thứ nhất (11/9/2025)

	Tiêu đề	File chương trình	File dữ liệu	File kết quả
Câu 1	Đoạn con chính phương	SEQCP.*	SEQCP.INP	SEQCP.OUT
Câu 2	Khóa	LOCK.*	LOCK.INP	LOCK.OUT
Câu 3	Kế hoạch dự phòng	BACKUP.*	BACKUP.INP	BACKUP.OUT

Dấu * được thay thế bởi PAS hoặc CPP tương ứng với ngôn ngữ lập trình Pascal hoặc C++.

Câu 1. Đoạn con chính phương (6.0 điểm)

Cho dãy N số nguyên dương. Hàm F(u, v) được định nghĩa là tích của các phần tử từ vị trí u đến vị trí v (u ≤ v), cụ thể hơn F(u, v) = a_u × a_u+1 × … × a_v.

Có Q truy vấn, với truy vấn thứ i gồm 2 số nguyên dương L_i, R_i (1 ≤ L_i ≤ R_i ≤ N), hãy cho biết F(L_i, R_i) có phải là số chính phương hay không?

Dữ liệu

Vào từ file văn bản SEQCP.INP:

• Dòng đầu tiên là hai số nguyên dương N và Q (1 ≤ N, Q ≤ 70000) lần lượt là số phần tử của dãy số và số truy vấn.
• Dòng thứ hai gồm N số nguyên dương a₁, a₂, a₃, …, a_N (1 ≤ a_i ≤ 70000).
• Dòng thứ i trong Q dòng tiếp theo, mỗi dòng gồm hai số nguyên dương L_i và R_i.

Kết quả

Ghi ra file văn bản SEQCP.OUT:

• Gồm Q dòng, dòng thứ i in xâu kí tự “YES” nếu F(L_i, R_i) là số chính phương, ngược lại in xâu kí tự “NO”.

Ví dụ

SEQCP.INP	SEQCP.OUT	Giải thích
5 3 2 4 8 16 32 1 3 2 4 1 5	YES NO NO	Truy vấn (1, 3): Tích của dãy con [2, 4, 8] là 2×4×8 = 64, mà 64 = 82 là số chính phương → YES Truy vấn (2, 4): Tích của dãy con [4, 8, 16] là 4×8×16 = 512, không phải số chính phương → NO Truy vấn (1, 5): Tích của dãy con [2, 4, 8, 16, 32] là 2×4×8×16×32 = 32768, không phải số chính phương → NO

Ràng buộc

• (1) Có 20% số test có 1 ≤ N, Q ≤ 18, 1 ≤ a_i ≤ 10 (1 ≤ i ≤ N).
• (2) Có 20% số test có 1 ≤ N, Q ≤ 2000, a_i = 2ᵏ (1 ≤ i ≤ N, k ≥ 0).
• (3) Có 20% số test có 1 ≤ N, Q ≤ 70000, … (phần cuối dòng bị mất trong bản chụp đề)
• (4) Có 20% số test có 1 ≤ N ≤ 70000, Q ≤ 100.
• (5) Có 20% số test còn lại không có ràng buộc gì thêm.

Câu 2. Khóa (7.0 điểm)

Một hệ thống khóa gồm N ô. Các ô được đánh số từ 1 đến N, mỗi ô có thể là 1 trong 3 trạng thái: 0, 1, 2. Ban đầu tất cả các ô đều ở trạng thái 0. NIGI thực hiện T lần thay đổi trạng thái của các ô, lần thay đổi thứ i (i = 1, 2, 3, …, T) sẽ thay đổi trạng thái của tất cả các ô từ vị trí a_i đến b_i (1 ≤ a_i ≤ b_i ≤ N). Nguyên tắc thay đổi như sau:

• Nếu ô đang trạng thái 0 sẽ chuyển sang trạng thái 1.
• Nếu ô đang trạng thái 1 sẽ chuyển sang trạng thái 2.
• Nếu ô đang trạng thái 2 sẽ chuyển sang trạng thái 0.

Ví dụ: Nếu hệ thống gồm 5 ô, ban đầu đều ở trạng thái 0. Nếu thay đổi 3 lần, lần 1 đổi từ vị trí 2 đến 4, lần 2 và lần 3 đều thay đổi ở vị trí 3 đến 5. Khi đó trạng thái của 5 ô lần lượt là: 0, 1, 0, 0, 2.

Yêu cầu: Cho biết T lần thay đổi, lần thứ i thay đổi trạng thái của tất cả các ô từ vị trí a_i đến b_i. Hãy cho biết, sau khi kết thúc T lần thì hệ thống có bao nhiêu ô ở trạng thái 0?

Dữ liệu

Vào từ file văn bản LOCK.INP:

• Dòng đầu chứa hai số nguyên dương N, T.
• Dòng thứ i trong T dòng tiếp theo chứa hai số nguyên dương a_i, b_i (1 ≤ a_i ≤ b_i ≤ N).

Kết quả

Ghi ra file văn bản LOCK.OUT:

• Một số nguyên là số lượng ô có trạng thái 0 sau T lần thay đổi.

Ví dụ

LOCK.INP	LOCK.OUT
5 3 2 4 3 5 3 5	3
1000 1 2 999	2

Ràng buộc

• (1) Có 25% số test có N ≤ 10⁶, T = 1.
• (2) Có 25% số test có N ≤ 10³, T ≤ 10⁵.
• (3) Có 40% số test có N ≤ 10⁶, T ≤ 10⁵.
• (4) Có 10% số test có N ≤ 10⁹, T ≤ 10⁵.

Câu 3. Kế hoạch dự phòng (7.0 điểm)

Đất nước NIGI có N thành phố, có N − 1 con đường. Đường đi giữa hai thành phố khác nhau có tải trọng là một số nguyên dương nhất định. Không có con đường nào nối một thành phố với chính nó. Có thể di chuyển từ thành phố này đến thành phố khác bằng đường đi trực tiếp, hoặc gián tiếp qua nhiều thành phố trung gian.

Do vấn đề an ninh leo thang, các nhà lãnh đạo quân sự muốn thực hiện kế hoạch dự phòng: Trong trường hợp có một số thành phố bị phá hủy, các con đường đi qua các thành phố đó không thể sử dụng được. Nếu có kế hoạch chuyển quân đội và khí tài quân sự từ thành phố u đến thành phố v thì họ cần biết: Có đường đi từ u đến v hay không? Nếu có thì tải trọng nhỏ nhất trên tuyến đường đó là bao nhiêu? Nếu không có thì đưa ra câu trả lời là −1. Trường hợp u = v thì đưa ra 0.

Ví dụ: Nếu đi từ u đến v bằng đường nối trực tiếp có tải trọng là 10, câu trả lời là 10. Nếu đi từ u đến v qua một số con đường có tải trọng lần lượt là: 8, 9, 2, 10 thì tải trọng nhỏ nhất là 2.

Yêu cầu: Kế hoạch gồm Q truy vấn thuộc một trong hai loại sau:

• 1 u v: Cho biết tải trọng nhỏ nhất của các đường đi trên tuyến từ thành phố u đến thành phố v. Nếu không thể đi từ u đến v, in ra −1. Nếu u = v, in ra 0.
• 2 u: Thành phố u bị phá hỏng hoàn toàn, không thể đi qua thành phố đó.

Dữ liệu

Vào từ file văn bản BACKUP.INP:

• Dòng 1: hai số nguyên dương N, Q - số thành phố và số truy vấn.
• N − 1 dòng tiếp: mỗi dòng chứa 3 số nguyên u v w (1 ≤ u, v ≤ N; 1 ≤ w ≤ 10⁶) nghĩa là có một đường đi nối trực tiếp thành phố u và thành phố v, tải trọng là w.
• Q dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong hai dạng:
  • 1 u v (1 ≤ u, v ≤ N)
  • 2 u (1 ≤ u ≤ N)

Kết quả

Ghi ra file văn bản BACKUP.OUT:

• Với mỗi truy vấn dạng 1 u v, in ra một dòng chứa kết quả tương ứng.

Ví dụ

BACKUP.INP	BACKUP.OUT
4 4 1 2 3 2 3 4 2 4 2 1 3 4 2 2 1 3 4 1 1 1	2 -1 0

Ràng buộc

• (1) Có 20% số test có N, Q ≤ 10³.
• (2) Có 20% số test có N, Q ≤ 10⁵ và chỉ có truy vấn loại 1 u v.
• (3) Có 20% số test có N, Q ≤ 10⁵ và tất cả truy vấn loại 2 u xảy ra trước các truy vấn loại 1 u v.
• (4) Có 20% số test có N, Q ≤ 10⁵ và một thành phố chỉ kết nối tối đa với 2 thành phố khác.
• (5) Có 20% số test có N, Q ≤ 10⁵.

Ngày thi thứ hai (12/9/2025)

	Tiêu đề	File chương trình	File dữ liệu	File kết quả
Câu 4	Dãy số	DAYSO.*	DAYSO.INP	DAYSO.OUT
Câu 5	Bảo mật	BAOMAT.*	BAOMAT.INP	BAOMAT.OUT
Câu 6	Biến đổi	BIENDOI.*	BIENDOI.INP	BIENDOI.OUT

Dấu * được thay thế bởi pas hoặc cpp hoặc py tương ứng với ngôn ngữ lập trình Pascal hoặc C++ hoặc Python.

Câu 4. Dãy số (6.0 điểm)

Cho dãy số A có N phần tử nguyên dương A₁, A₂, …, A_N với 1 ≤ A_i ≤ N, i = 1, 2, …, N. Các phần tử của dãy số A được đánh số từ chỉ số 1 đến chỉ số N.

Yêu cầu

Cho Q truy vấn, với mỗi truy vấn cho biết 4 chỉ số x, y, u, v, hãy tính

Tổng của f(i, x, y) × f(i, u, v) với i = 1, 2, …, N,

với f(i, l, r) là số lần xuất hiện của giá trị i trong dãy số A từ chỉ số l đến chỉ số r.

Dữ liệu

Đọc từ file văn bản DAYSO.INP:

• Dòng đầu tiên gồm 2 số nguyên N, Q (với 1 ≤ N, Q ≤ 5.10⁴).
• Dòng thứ hai gồm N số nguyên dương A₁, A₂, …, A_N (với 1 ≤ A_i ≤ N, i = 1, 2, …, N).
• Q dòng tiếp theo, mỗi dòng gồm 4 số nguyên x, y, u, v tương ứng với một truy vấn (với 1 ≤ x ≤ y ≤ N, 1 ≤ u ≤ v ≤ N).

Kết quả

• Ghi ra file văn bản DAYSO.OUT gồm Q dòng, dòng thứ i là kết quả của truy vấn thứ i tương ứng cho trong file dữ liệu.

Ví dụ

DAYSO.INP	DAYSO.OUT
6 3 2 1 3 1 2 1 2 2 6 6 1 6 2 6 3 3 5 5	1 12 0

Ràng buộc

• (1) Có 20% số điểm của bài có N, Q ≤ 300.
• (2) Có 20% số điểm của bài có N, Q ≤ 1000.
• (3) Có 20% số điểm của bài có A_i ≤ 50, 1 ≤ i ≤ N.
• (4) Có 40% số điểm của bài không có ràng buộc gì thêm.

Câu 5. Bảo mật (7.0 điểm)

Trong một hệ thống truyền thông tin bảo mật giữa các thiết bị IoT, dữ liệu đôi khi được chèn thêm các chuỗi đối xứng (palindromes) để đánh dấu các đoạn dữ liệu đặc biệt, ví dụ như mã xác thực, mã kiểm tra hoặc mã khóa tạm thời. Chuỗi đối xứng là chuỗi mà khi đọc từ trái sang phải cũng thu được kết quả giống như đọc từ phải qua trái.

Để phân tích nhật kí truyền thông tin được ghi lại dưới dạng chuỗi các kí tự thường, Alex cần biết trong mỗi đoạn kí tự được chỉ định có bao nhiêu chuỗi con liên tiếp là chuỗi đối xứng.

Yêu cầu

Cho một chuỗi kí tự S có độ dài N đại diện cho nhật kí truyền thông tin được ghi lại và Q truy vấn. Với mỗi truy vấn cho 2 chỉ số u, v (với 1 ≤ u ≤ v ≤ N) tương ứng với một đoạn kí tự được chỉ định gồm các kí tự từ vị trí u đến vị trí v của chuỗi S, hãy xác định số lượng chuỗi con liên tiếp là chuỗi đối xứng.

Dữ liệu

Đọc từ file văn bản BAOMAT.INP:

• Dòng đầu tiên chứa chuỗi kí tự S gồm N chữ cái in thường thuộc bảng chữ cái tiếng Anh (với N ≤ 10⁵).
• Dòng thứ hai chứa số nguyên dương Q là số lượng truy vấn.
• Q dòng tiếp theo, mỗi dòng chứa 2 số nguyên u, v mô tả một truy vấn (với 1 ≤ u ≤ v ≤ N).

Kết quả

Ghi ra file văn bản BAOMAT.OUT gồm Q dòng, dòng thứ i ghi đáp án tương ứng với truy vấn thứ i cho trong file dữ liệu.

Ví dụ

BAOMAT.INP	BAOMAT.OUT
abacaab 4 1 3 3 6 2 7 5 6	4 6 8 3

Ràng buộc

• (1) Có 25% số điểm có N, Q ≤ 500.
• (2) Có 25% số điểm có N, Q ≤ 5000.
• (3) Có 25% số điểm có N, Q ≤ 50000.
• (4) Có 25% số điểm còn lại không có giới hạn gì thêm.

Câu 6. Biến đổi (7.0 điểm)

Cho một bảng hình chữ nhật gồm M hàng và N cột, các hàng được đánh số thứ tự từ 1 đến M, các cột được đánh số thứ tự từ 1 đến N. Ô (i, j) với 1 ≤ i ≤ M, 1 ≤ j ≤ N là ô nằm ở hàng i và cột j. Trên mỗi ô (i, j) chứa một số nguyên a[i, j] với 0 ≤ a[i, j] < 10⁵. Hai ô (u, v) và (x, y) gọi là kề cạnh khi và chỉ khi chúng có chung một cạnh. Ví dụ ô (2, 3) có 4 ô kề cạnh là các ô (2, 2), (1, 3), (2, 4), (3, 3) còn ô (1, 1) chỉ có 2 ô kề cạnh là ô (2, 1) và (1, 2).

Một miền liên thông là tập hợp các ô kề cạnh trên bảng có giá trị bằng nhau. Một phép biến đổi (u, v, x) trên bảng là một phép gán giá trị x cho tất cả các ô thuộc cùng miền liên thông với ô (u, v).

Ví dụ bảng hình chữ nhật dưới đây có 5 miền liên thông

1	1	1	3
1	3	2	2
3	3	2	0
2	2	2	2

Sau khi thực hiện phép biến đổi (4, 2, 1), bảng trở thành:

1	1	1	3
1	3	1	1
3	3	1	0
1	1	1	1

Yêu cầu

Cho bảng hình chữ nhật gồm M hàng, N cột, mỗi ô chứa một số nguyên không âm và Q phép biến đổi, mỗi phép biến đổi cho bởi 3 số nguyên u, v, x với 1 ≤ u ≤ M, 1 ≤ v ≤ N, 0 ≤ x < 10⁵. Sau khi thực hiện lần lượt Q phép biến đổi, hãy cho biết trạng thái của bảng.

Dữ liệu

Đọc từ file văn bản BIENDOI.INP:

• Dòng đầu tiên chứa 2 số nguyên dương M và N tương ứng là số hàng và số cột của bảng hình chữ nhật.
• M dòng tiếp theo, mỗi dòng chứa N số nguyên không âm a[i, j] tương ứng với các số ghi trên bảng hình chữ nhật (với 1 ≤ i ≤ M, 1 ≤ j ≤ N, 0 ≤ a[i, j] < 10⁵).
• Dòng tiếp theo chứa số nguyên Q là số phép biến đổi.
• Q dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, x tương ứng với một phép biến đổi.

Kết quả

Ghi ra file văn bản BIENDOI.OUT gồm M hàng, mỗi hàng gồm N giá trị, mô tả trạng thái của bảng hình chữ nhật sau Q phép biến đổi tương ứng cho trong file dữ liệu.

Ví dụ

BIENDOI.INP	BIENDOI.OUT
12 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 2 2 2 0 0 0 1 1 0 0 0 2 2 2 0 0 0 1 1 0 0 0 2 2 2 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 2 0 0 0 1 1 0 1 1 0 0 2 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 2 5 5 3 6 2 4	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 1 1 1 1 1 1 1 4 4 4 4 4 1 1 1 1 1 4 4 4 4 4 4 4 1 1 1 4 4 4 3 3 3 4 4 4 1 1 4 4 4 3 3 3 4 4 4 1 1 4 4 4 3 3 3 4 4 4 1 1 4 4 4 4 4 4 4 4 4 1 1 1 4 4 4 2 4 4 4 1 1 0 1 1 4 4 2 4 4 1 1 0 0 0 1 1 4 4 4 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0
4 4 1 0 1 3 1 3 2 2 3 3 1 2 2 2 1 3 3 1 2 3 3 2 1 4 2 3	1 1 1 3 1 1 2 2 1 1 1 2 3 3 1 3
6 6 1 2 1 2 2 2 3 1 2 1 3 1 3 3 2 3 2 2 2 3 1 3 3 2 3 3 3 3 3 3 2 3 2 2 2 1 4 6 2 2 3 5 2 3 2 3 1 2 3	1 3 1 2 2 2 3 1 3 1 3 1 3 3 3 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1

Ràng buộc

• (1) Có 8% số điểm ứng với các test thỏa mãn 1 ≤ M × N ≤ 10000, 1 ≤ Q ≤ 10000.
• (2) Có 9% số điểm ứng với các test thỏa mãn M = 1, 1 ≤ N ≤ 200000, 1 ≤ Q ≤ 100000.
• (3) Có 31% số điểm ứng với các test thỏa mãn 1 ≤ M × N ≤ 200000, 1 ≤ Q ≤ 100000 và mọi giá trị ghi trên bảng chữ nhật đều bằng 0 hoặc 1.
• (4) Có 52% số điểm ứng với các test có 1 ≤ M × N ≤ 200000, 1 ≤ Q ≤ 100000.

---

Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm.