Chọn đội tuyển HSG quốc gia Vĩnh Long 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH LONG ĐỀ THI CHÍNH THỨC
(Mỗi buổi thi gồm 03 trang, 03 bài)

KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA THPT Năm học 2025 - 2026 - Khóa thi ngày: 20/9/2025
Môn: Tin học (buổi sáng và buổi chiều)
Thời gian: 180 phút mỗi buổi (không kể thời gian giao đề)

---

Buổi sáng

	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
Bài 1	Nguyên tố	ANGUYENTO.*	ANGUYENTO.INP	ANGUYENTO.OUT	7.00
Bài 2	Nhận quà	BNHANQUA.*	BNHANQUA.INP	BNHANQUA.OUT	7.00
Bài 3	Ghép đôi	CGHEPDOI.*	CGHEPDOI.INP	CGHEPDOI.OUT	6.00

Dấu * được thay thế bởi phần mở rộng của ngôn ngữ lập trình được sử dụng (Ví dụ PY, CPP, PAS, …).

Bài 1. Nguyên tố (7.00 điểm)

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có đúng hai ước số dương là 1 và chính nó. Cho hai số nguyên dương X và Y.

Yêu cầu: Hãy đếm trong đoạn từ X đến Y có bao nhiêu số thỏa mãn: số lượng các ước của nó là số nguyên tố.

Dữ liệu: Vào từ file văn bản ANGUYENTO.INP gồm:

• Dòng thứ nhất chứa số T (T ≤ 10⁵) là số lượng các đoạn cần đếm;
• T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương X và Y (1 ≤ X ≤ Y ≤ 10⁶).

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản ANGUYENTO.OUT gồm T dòng, mỗi dòng gồm một số nguyên duy nhất là kết quả cần tìm.

Ví dụ:

ANGUYENTO.INP	ANGUYENTO.OUT	Giải thích
2 1 5 10 50	4 14	Xét trường hợp X = 1, Y = 5: Số 1 có 1 ước (số ước không phải nguyên tố); Số 2 có 2 ước (số ước là nguyên tố); Số 3 có 2 ước (số ước là nguyên tố); Số 4 có 3 ước (số ước là nguyên tố); Số 5 có 2 ước (số ước là nguyên tố). Kết quả: 4.

Ràng buộc:

• Subtask 1: Có 6/14 test có T ≤ 10², 1 ≤ X ≤ Y ≤ 10³;
• Subtask 2: Có 4/14 test có T ≤ 10³, 1 ≤ X ≤ Y ≤ 2×10³;
• Subtask 3: Số test còn lại không có ràng buộc gì thêm.

Bài 2. Nhận quà (7.00 điểm)

Trong thời gian nghỉ hè, bạn B tham gia một trò chơi trực tuyến và được nhận quà. Để thử thách khả năng của người chơi, hệ thống đưa ra cách nhận quà như sau:

Cho N món quà có giá trị lần lượt là a₁, a₂, …, a_N và hai số X, M. Người chơi chỉ được nhận dãy các món quà liên tiếp nhau có tổng lũy thừa bậc X của giá trị các món quà chia hết cho M. Hai dãy quà liên tiếp là khác nhau nếu tồn tại ít nhất một món quà không thuộc cả hai dãy.

Ví dụ với 3 món quà: {1, 5, 5} thì có 6 dãy các món quà liên tiếp là {1}, {5}, {5}, {1, 5}, {5, 5}, {1, 5, 5}, với X = 1 và M = 5 thì chỉ có 3 phương án nhận quà là: {5}, {5} và {5, 5}.

Yêu cầu: Hãy cho biết bạn B có bao nhiêu phương án nhận quà.

Dữ liệu: Vào từ file văn bản BNHANQUA.INP gồm hai dòng:

• Dòng thứ nhất chứa ba số nguyên dương N, X, M (1 ≤ N ≤ 10⁵; 1 ≤ X ≤ 10¹⁸, 1 ≤ M ≤ 10⁵) lần lượt là số món quà và giá trị X, M theo yêu cầu;
• Dòng thứ hai chứa N số tự nhiên a₁, a₂, …, a_N (1 ≤ aᵢ ≤ 10²⁰) lần lượt là giá trị các món quà.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản BNHANQUA.OUT một số nguyên duy nhất là kết quả cần tìm.

Ví dụ:

BNHANQUA.INP	BNHANQUA.OUT
3 1 5 1 5 5	3
5 2 3 3 3 3 3 3	15

Ràng buộc:

• Subtask 1: Có ít nhất 4/14 số test có X = 1, N ≤ 10³, aᵢ ≤ 10⁶;
• Subtask 2: Có ít nhất 6/14 số test có 1 < X ≤ 10, N ≤ 10⁵, 10⁶ < aᵢ ≤ 10⁹;
• Subtask 3: Số test còn lại có 10 < X ≤ 10¹⁸, N ≤ 10⁵, 10⁹ < aᵢ ≤ 10²⁰.

Bài 3. Ghép đôi (6.00 điểm)

Đầu năm học mới, để tăng cường tình đoàn kết trong học sinh, nhà trường tổ chức trò chơi cho N học sinh tham gia. Mỗi học sinh được cấp một mã số là các số nguyên a₁, a₂, …, a_N (0 ≤ aᵢ ≤ 10⁹). Người quản trò yêu cầu các học sinh cần ghép đôi lại thành từng cặp với nhau để tham gia trò chơi, điều kiện là tổng mã số của từng cặp đôi một với các cặp khác không chênh lệch quá giá trị K do người quản trò đặt ra, để học sinh không mất quá nhiều thời gian tìm người ghép đôi, người quản trò quy ước K chỉ nhận giá trị 0 hoặc 1. Có thể có những học sinh sẽ không được ghép với bạn khác (những học sinh này sẽ hỗ trợ làm trọng tài) và mỗi học sinh nếu được ghép chỉ thuộc một cặp duy nhất.

Yêu cầu: Cho biết số lượng cặp học sinh nhiều nhất tìm được mà tổng mã số của từng cặp đôi một với các cặp khác chênh lệch nhau không vượt quá K.

Dữ liệu: Vào từ file văn bản CGHEPDOI.INP gồm:

• Dòng thứ nhất chứa hai số nguyên N, K (0 < N ≤ 2×10³, 0 ≤ K ≤ 1) lần lượt là số lượng học sinh tham gia và giá trị do người quản trò đặt ra;
• Dòng thứ hai chứa N số nguyên a₁, a₂, …, a_N (0 ≤ aᵢ ≤ 10⁹) lần lượt là mã số của các học sinh.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản CGHEPDOI.OUT gồm một số nguyên duy nhất là giá trị cần tìm.

Ví dụ:

CGHEPDOI.INP	CGHEPDOI.OUT	Giải thích
7 0 2 4 1 3 5 6 1	3	Một trong các phương án ghép đôi là 2-5, 4-3, 1-6 (tổng mã số của các cặp đôi một chênh lệch là 0)
6 1 1 2 3 10 30 3	2	Phương án ghép đôi là 1-3, 2-3 (tổng mã số của các cặp đôi một chênh lệch không quá 1)

Ràng buộc:

• Subtask 1: Có 4/12 test có 2 ≤ N ≤ 10, K = 0;
• Subtask 2: Có 4/12 test có 10 < N ≤ 100, K = 1;
• Subtask 3: Số test còn lại không có ràng buộc gì thêm.

Buổi chiều

	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
Bài 4	In tài liệu	DINTL.*	DINTL.INP	DINTL.OUT	7.00
Bài 5	Dãy con	EDCON.*	EDCON.INP	EDCON.OUT	7.00
Bài 6	Vùng liên thông	FVLT.*	FVLT.INP	FVLT.OUT	6.00

Dấu * được thay thế bởi phần mở rộng của ngôn ngữ lập trình được sử dụng (Ví dụ PY, CPP, PAS, …).

Bài 4. In tài liệu (7.00 điểm)

Công ty D là một trong những công ty in ấn đặt tại trung tâm thành phố. Hiện tại, công ty dùng N máy để in tài liệu cho khách. Do có nhiều loại máy in được sử dụng trong công ty, thời gian để in xong một tài liệu trên các máy in có thể khác nhau.

Yêu cầu: Cho biết T là số lượng khách hàng cần in tài liệu, hãy xác định thời gian tối thiểu cần thiết để công ty có thể in xong tài liệu cho tất cả khách.

Để in mỗi tài liệu chỉ được sử dụng một máy in.

Dữ liệu: Vào từ file văn bản DINTL.INP:

• Dòng thứ nhất chứa hai số nguyên dương T (0 < T ≤ 10¹²) và N (0 < N ≤ 20) lần lượt là số lượng khách in tài liệu và số lượng máy in;
• Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, a_N (0 < aᵢ < 500) lần lượt là thời gian in xong một tài liệu của mỗi máy.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản DINTL.OUT một số nguyên duy nhất là thời gian tối thiểu tìm được tính bằng phút (không kể thời gian chuyển sang in tài liệu khác).

Ví dụ:

DINTL.INP	DINTL.OUT	Giải thích
4 3 20 30 35	40	Có 4 khách in tài liệu và 3 máy in. Máy 1 in tài liệu cho khách 1 mất 20p, máy 2 in tài liệu cho khách 2 mất 30p, máy 3 in tài liệu cho khách 3 mất 35p. Sau 20p máy 1 in xong tài liệu cho khách 1 thì in cho khách 4. Sau 40p thì tất cả tài liệu đều được in xong.

Ràng buộc:

• Subtask 1: Có 8/14 test có 0 < T ≤ 10⁴, 0 < aᵢ ≤ 100;
• Subtask 2: Số test còn lại không có ràng buộc gì thêm.

Bài 5. Dãy con (7.00 điểm)

Cho dãy số nguyên a₁, a₂, …, a_N. Dãy số a_(i1), a_(i2), …, a_(ik) được gọi là dãy con của dãy a nếu 1 ≤ i1 < i2 < … < ik ≤ N.

Một dãy số b₁, b₂, …, bₘ được gọi là dãy hình nón nếu tồn tại vị trí j sao cho: b₁ < b₂ < … < bⱼ > bⱼ₊₁ > … > bₘ (với 1 < j < m).

Yêu cầu: Tìm dãy con hình nón có tổng lớn nhất.

Dữ liệu: Vào từ file văn bản EDCON.INP:

• Dòng thứ nhất chứa số nguyên N (3 ≤ N ≤ 1000);
• Dòng thứ hai chứa N số nguyên a₁, a₂, …, a_N (1 ≤ aᵢ ≤ 10⁹).

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Đưa ra file văn bản EDCON.OUT một số nguyên duy nhất là kết quả tìm được. Trường hợp không tồn tại dãy con hình nón thì ghi 0.

Ví dụ:

EDCON.INP	EDCON.OUT	Giải thích
8 2 1 1 9 2 1 2 5	16	Dãy con hình nón có tổng lớn nhất là 2 9 5
6 7 5 3 1 2 3	0	Không tồn tại dãy con hình nón

Ràng buộc:

• Subtask 1: Có 6/14 test có N ≤ 20;
• Subtask 2: Số test còn lại không có ràng buộc gì thêm.

Bài 6. Vùng liên thông (6.00 điểm)

Cho đồ thị G vô hướng, liên thông gồm N đỉnh (đánh số hiệu từ 1 đến N) và M cạnh (đánh số hiệu từ 1 đến M). Giữa hai đỉnh khác nhau của G có không quá một cạnh nối hai đỉnh đó.

Cho K là số hiệu của một đỉnh trong đồ thị (1 ≤ K ≤ N). Gọi H là đồ thị con của đồ thị G. Xét đồ thị con H(K): H(K) gồm các đỉnh có số hiệu từ 1 đến K và các cạnh (x, y) nối 2 đỉnh nằm trọn trong khoảng từ 1 đến K (1 ≤ x, y ≤ K).

Yêu cầu: Với mỗi cặp giá trị K và V (1 ≤ V ≤ K ≤ N), liệt kê các đỉnh thuộc vùng liên thông chứa đỉnh V của đồ thị con H(K).

Dữ liệu: Vào từ file văn bản FVLT.INP:

• Dòng thứ nhất chứa hai số nguyên dương N, M (1 ≤ N ≤ 10⁵; 1 ≤ M ≤ 2×10⁵) lần lượt là số đỉnh và số cạnh của đồ thị G;
• Dòng thứ hai chứa M giá trị xᵢ;
• Dòng thứ ba chứa M giá trị yᵢ; Trong đó: (xᵢ, yᵢ) là cạnh thứ i (1 ≤ i ≤ M) của đồ thị liên thông G;
• Dòng thứ tư chứa số nguyên dương Q (1 ≤ Q ≤ 10⁵) là số bộ dữ liệu;
• Q dòng tiếp theo, mỗi dòng chứa hai số K, V (1 ≤ V ≤ K ≤ N) lần lượt là số đỉnh của đồ thị con và đỉnh mà vùng liên thông sẽ chứa.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản FVLT.OUT gồm Q dòng, mỗi dòng liệt kê các đỉnh của vùng liên thông chứa đỉnh V (các đỉnh có thứ tự từ nhỏ đến lớn).

Ví dụ:

FVLT.INP	FVLT.OUT
8 7 1 1 4 4 3 7 5 6 5 1 8 5 3 2 2 4 1 8 3	1 4 1 2 3 4 5 6 7 8

Giải thích: Đồ thị liên thông có 8 đỉnh, 7 cạnh: (1, 6), (1, 5), (4, 1), (4, 8), (3, 5), (7, 3), (5, 2). Q = 2 bộ dữ liệu. Với trường hợp bộ dữ liệu 1: K = 4, V = 1, vùng liên thông của đồ thị con chứa đỉnh V có các đỉnh: 1 4.

Ràng buộc:

• Subtask 1: Có 6/12 test có N ≤ 10², M ≤ 10²;
• Subtask 2: Số test 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.