Chọn đội tuyển HSG quốc gia Lào Cai 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH LÀO CAI ĐỀ CHÍNH THỨC
(Mỗi ngày thi có 04 trang, gồm 03 bài)

KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA Năm học 2025 - 2026
Môn: Tin học - Ngày thi: 16/9/2025 và 17/9/2025
Thời gian: 180 phút (không kể thời gian giao đề)

---

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

Bài	Tên tệp nộp	Tên tệp dữ liệu vào	Tên tệp dữ liệu ra	Điểm
1	LAND.*	LAND.INP	LAND.OUT	7
2	UNLOCK.*	UNLOCK.INP	UNLOCK.OUT	7
3	CONNECT.*	CONNECT.INP	CONNECT.OUT	6

Dấu (*) thay bởi cpp hoặc py tùy thuộc vào ngôn ngữ lập trình là C++ hay Python.

Bài 1. Chia đất

Alice có một mảnh đất hình chữ nhật với cạnh chiều dài là N đơn vị và cạnh chiều rộng là M đơn vị. Mảnh đất được chia thành N × M ô vuông đơn vị. Chiều dài chia thành N hàng, các hàng được đánh số từ 1 đến N từ trên xuống dưới. Chiều rộng được chia thành M cột, các cột được đánh số từ 1 đến M từ trái sang phải. Ô nằm giao giữa hàng i và cột j được gọi là ô (i, j). Có K ô của mảnh đất đã được trồng cây. Với cặp số (u, v), Alice muốn cắt một mảnh đất hình vuông từ mảnh đất ban đầu đồng thời thỏa mãn các điều kiện sau:

• Chứa nguyên các ô vuông của mảnh đất ban đầu;
• Có chiều dài cạnh chia hết cho u;
• Có không quá v ô đã được trồng cây;
• Có cạnh lớn nhất.

Yêu cầu: Hãy tìm mảnh đất hình vuông thỏa mãn các điều kiện trên.

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

• Dòng đầu chứa năm số nguyên dương N, M, K, u, v (v ≤ K ≤ N × M, u ≤ min(N, M)).
• Dòng thứ q trong K dòng tiếp theo chứa hai số nguyên i_q, j_q là vị trí ô đã trồng cây (1 ≤ q ≤ K).

Dữ liệu vào đảm bảo có thể cắt được mảnh đất hình vuông theo yêu cầu.

Kết quả: Ghi ra tệp văn bản LAND.OUT độ dài cạnh của mảnh đất hình vuông thỏa mãn các điều kiện trên.

Ví dụ:

LAND.INP	LAND.OUT
6 6 5 3 3 1 1 1 4 4 4 6 1 4 6	3

Minh họa: Một phương án chọn cắt hình vuông.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài với N, M ≤ 20;
• Có 30% số test khác ứng với 30% số điểm của bài với N, M ≤ 200;
• Có 20% số test khác ứng với 20% số điểm của bài với N, M ≤ 2000 và K ≤ 10⁵;
• Có 20% số test còn lại ứng với 20% số điểm của bài với N, M ≤ 6000 và K ≤ 10⁵.

Bài 2. Cuộc đua kì thú

Nhà phát hành trò chơi XGAMING vừa đưa ra một trò chơi mới mang tên “Cuộc đua kì thú”. Người chơi có T cánh cửa bí mật cần mở khóa, ở mỗi lượt người chơi cần tìm và nhập mật khẩu để mở khóa một cánh cửa bí mật.

Ở lượt chơi thứ i, chương trình sẽ cung cấp cho người chơi một số nguyên dương n_i. Mật khẩu để mở khóa cánh cửa này là số cách phân tích n_i thành tổng các lũy thừa của 2. Ví dụ với n = 6, có đúng 6 cách phân tích khác nhau thỏa mãn là:

(2⁰, 2⁰, 2⁰, 2⁰, 2⁰, 2⁰), (2⁰, 2⁰, 2⁰, 2⁰, 2¹), (2⁰, 2⁰, 2¹, 2¹), (2¹, 2¹, 2¹), (2¹, 2²), (2⁰, 2⁰, 2²)

Yêu cầu: Hãy tìm mật khẩu để mở khóa các cánh cửa bí mật của trò chơi.

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

• Dòng 1: Chứa số nguyên dương T là số lượng cánh cửa bí mật cần mở khóa (T ≤ 100).
• T dòng tiếp theo, mỗi dòng chứa một số nguyên dương n_i mà chương trình cung cấp ở lượt chơi thứ i (1 ≤ i ≤ T).

Kết quả: Ghi ra tệp văn bản UNLOCK.OUT gồm T dòng, dòng thứ i ghi ra giá trị S_i mod (10⁹ + 7), với S_i là mật khẩu tương ứng với số nguyên dương n_i của lượt chơi thứ i.

Biết rằng mod là phép toán chia lấy phần dư.

Ví dụ:

UNLOCK.INP	UNLOCK.OUT
5 6 5 12 8 11	6 4 20 10 14

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài với n_i ≤ 100;
• Có 30% số test khác ứng với 30% số điểm của bài với n_i ≤ 10⁵;
• Có 30% số test khác ứng với 30% số điểm của bài với n_i ≤ 10⁷;
• Có 20% số test còn lại ứng với 20% số điểm của bài với n_i ≤ 10¹⁸.

Bài 3. Kết nối

Đất nước HYPER có N thành phố khác nhau. Để kết nối các thành phố bằng đường bộ, Chính phủ đã đề ra M phương án xây dựng những con đường một chiều giữa các thành phố. Với phương án thứ i (1 ≤ i ≤ M) biểu diễn dưới dạng (u, v, w). Khi đó bạn chỉ có thể:

• Xây con đường một chiều nối từ u đến v với chi phí là w.
• Hoặc xây con đường một chiều nối từ v đến u với chi phí là w.
• Hoặc không sử dụng phương án này.

Yêu cầu: Hãy tìm cách sử dụng các phương án xây dựng sao cho từ một thành phố có đường đi đến các thành phố còn lại, đồng thời chi phí lớn nhất để xây dựng một con đường nối giữa hai thành phố là nhỏ nhất.

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

• Dòng đầu tiên gồm hai số nguyên dương N, M (N ≤ 10⁵, M ≤ 2.10⁵);
• M dòng tiếp theo, dòng thứ i chứa ba số nguyên dương u, v, w (u, v ≤ N, w ≤ 10⁹) mô tả phương án thứ i.

Dữ liệu vào đảm bảo không có phương án nào xây đường đi từ một thành phố đến chính nó.

Kết quả: Ghi ra tệp văn bản CONNECT.OUT: Nếu không có cách sử dụng các phương án thỏa mãn thì in ra số −1, ngược lại in ra chi phí lớn nhất để xây dựng một con đường nối giữa hai thành phố là nhỏ nhất.

Ví dụ 1:

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

• Phương án 1: Chọn xây 5 đường nối các thành phố là 1→2 (1), 2→3 (3), 2→4 (4), 3→4 (3), 4→1 (2). Chi phí lớn nhất để xây một con đường là 4.
• Phương án 2: Chọn xây 4 đường nối các thành phố là 1→2 (1), 2→3 (3), 3→4 (3), 4→1 (2). Chi phí lớn nhất để xây một con đường là 3.

Chi phí nhỏ nhất tìm được là: 3.

Ví dụ 2:

CONNECT.INP	CONNECT.OUT
4 4 1 2 1 2 3 2 3 4 3 4 2 4	-1

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài với M = N;
• Có 30% số test ứng với 30% số điểm của bài với N ≤ 1000;
• Có 50% số test còn lại ứng với 50% số điểm của bài không có ràng buộc gì thêm.

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

Bài	Tên tệp nộp	Tên tệp dữ liệu vào	Tên tệp dữ liệu ra	Điểm
4	SCHESMAR.*	SCHESMAR.INP	SCHESMAR.OUT	7
5	SQUASEGM.*	SQUASEGM.INP	SQUASEGM.OUT	7
6	SCHOOLRT.*	SCHOOLRT.INP	SCHOOLRT.OUT	6

Dấu (*) thay bởi cpp hoặc py tùy thuộc vào ngôn ngữ lập trình là C++ hay Python.

Bài 4. Bán hàng

Để tạo hiệu ứng kinh doanh tốt hơn, nông trại X thực hiện chiến lược kinh doanh như sau: Bày N giỏ trái cây thành một hàng trên kệ bán dọc đường vào nông trại, các giỏ trái cây được đánh số từ 1 đến N. Độ ngon của giỏ trái cây thứ i là A_i. Mỗi khách chỉ được mua những giỏ trái cây liên tiếp. Mỗi giỏ trái cây chỉ bán cho tối đa một khách (có thể không bán cho ai).

Độ hài lòng của một khách hàng sau khi mua trái cây được tính bằng tổng độ ngon của các giỏ trái cây mà khách hàng đó nhận được (nếu không nhận được giỏ trái cây nào thì độ hài lòng bằng 0).

Có K khách hàng đến mua trái cây, người chủ nông trại muốn bán các giỏ trái cây cho khách hàng sao cho tổng độ hài lòng của K khách hàng là lớn nhất.

Yêu cầu: Hãy tính tổng độ hài lòng lớn nhất của K khách hàng.

Dữ liệu: Vào từ tệp văn bản SCHESMAR.INP có cấu trúc như sau:

• Dòng đầu ghi hai số nguyên dương N, K (K ≤ N ≤ 3.10⁵).
• Dòng thứ hai ghi lần lượt N số nguyên A₁, A₂, …, A_N (|A_i| ≤ 10⁹).

Các số ghi trên một dòng cách một dấu cách.

Kết quả: Ghi ra tệp văn bản SCHESMAR.OUT tổng độ hài lòng lớn nhất của K khách hàng.

Ví dụ:

SCHESMAR.INP	SCHESMAR.OUT	Giải thích
6 2 -1 4 6 -1 8 9	27	Khách hàng 1 nhận giỏ thứ 2, 3; khách hàng 2 nhận giỏ thứ 5, 6 có tổng độ ngon lớn nhất là (4 + 6) + (8 + 9) = 27.

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài có tối đa một giỏ trái cây có độ ngon âm;
• Có 20% số test khác ứng với 20% số điểm của bài với K = 1;
• Có 20% số test khác ứng với 20% số điểm của bài với 1 ≤ K ≤ N ≤ 80;
• Có 20% số test khác ứng với 20% số điểm của bài với 80 < K ≤ N ≤ 300;
• Có 20% số test còn lại ứng với 20% số điểm của bài với 300 < K ≤ N ≤ 2000.

Bài 5. Tập số

Xét tập số nguyên S được định nghĩa như sau:

• Số 1 thuộc S;
• Nếu x thuộc S, thì 2x + 1 và 3x + 1 cũng thuộc S;
• Tập S được sắp xếp tăng dần, không chứa số nào khác ngoài các số theo quy tắc đã nêu và mỗi số xuất hiện một lần.

Các số đầu tiên của tập S vô hạn là: 1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, 28, 31, 39, 40, 43, 45, 46, 55, 57, 58, 63, 64, 67, 79, 81, 82, 85, 87, 91, 93, 94, …

John điền N² phần tử đầu tiên của tập S vào một bảng gồm N hàng, N cột theo thứ tự từ trái sang phải, từ trên xuống dưới.

Yêu cầu: Hãy tìm hình vuông con có cạnh lớn nhất của bảng có tổng các phần tử cũng là một số thuộc tập S.

Dữ liệu: Vào từ tệp SQUASEGM.INP ghi số nguyên dương N.

Kết quả: Ghi ra tệp SQUASEGM.OUT cạnh của hình vuông con lớn nhất có tổng các phần tử cũng là một số thuộc dãy tập S.

Ví dụ:

SQUASEGM.INP	SQUASEGM.OUT
14	12

Ràng buộc:

• 20% số test ứng với 20% số điểm của bài với N ≤ 35;
• 80% số test còn lại ứng với 80% số điểm của bài với 35 < N ≤ 100.

Giải thích: Với N = 14, hình vuông cạnh K = 12, tọa độ góc trái trên của hình vuông là (3, 1), có tổng các số trong hình vuông bằng 73965 là một số thuộc tập S.

Bài 6. Hành trình

Thành phố nơi An sống có N khu phố, được đánh số từ 1 đến N và được kết nối với nhau bởi M con đường hai chiều. Nhà An ở một khu phố. Một hành trình là một đường đi từ nhà đến các khu phố khác, sau đó quay lại về nhà của An sao cho không đi qua khu phố nào hai lần (trừ khu phố có nhà An).

Trong thành phố có (N − 1) con đường quen thuộc với An. Để có thêm trải nghiệm mới, An chọn hành trình có đúng hai con đường không quen thuộc trong thành phố.

Yêu cầu: Hãy giúp An đếm số cách chọn hành trình có đúng hai con đường không quen thuộc trong thành phố.

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

• Dòng đầu chứa hai số nguyên dương N, M (N ≤ 2.10⁵, M ≤ 2.10⁵, N ≤ M).
• (N − 1) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương (u, v) mô tả một con đường quen thuộc nối khu phố u với khu phố v (u, v ≤ N, u ≠ v).
• (M − N + 1) dòng tiếp theo, mỗi dòng chứa hai số nguyên (u, v) mô tả một con đường không quen thuộc nối khu phố u với khu phố v.

Kết quả: Ghi ra tệp văn bản SCHOOLRT.OUT số cách chọn hành trình có đúng hai con đường không quen thuộc trong thành phố.

Ví dụ:

SCHOOLRT.INP	SCHOOLRT.OUT
5 8 1 2 1 3 1 4 1 5 2 3 3 4 4 5 5 2	4

Giải thích: Các hành trình khác nhau tìm được là

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài với M ≤ 20.
• Có 25% số test khác ứng với 25% số điểm của bài với M ≤ 200.
• Có 25% số test khác ứng với 25% số điểm của bài với M ≤ 2000.
• Có 25% số test còn lại ứng với 25% số điểm của bà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.