Thi thử HSG Tin quốc gia #02 – 01/11/2026 (Công khai cho mọi người)

Con nước (Đề tự luyện HSG Tin quốc gia #02 – Bài 1)

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 5

⚠️ LƯU Ý: Đây chỉ là cuộc thi thử – các em hãy cố gắng TỰ LỰC làm bài, KHÔNG sử dụng AI, không tra cứu lời giải hay nhờ người khác hỗ trợ, để đánh giá chính xác năng lực thật của bản thân!
🚨 Trong suốt thời gian thi, thầy sẽ LIÊN TỤC KIỂM TRA bài làm của các em. Trường hợp nào bị phát hiện GIAN LẬN sẽ bị XÓA KHỎI CUỘC THI!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Mùa nước nổi năm nay, thầy Sơn thả cá linh trong một cái đìa nhỏ sát bờ sông Hậu. Giữa đìa thầy cắm một cây sào có khắc vạch ~0, 1, 2, \ldots, H~ để theo dõi mực nước. Mực nước luôn là một số nguyên và phải luôn nằm trong khoảng từ ~1~ đến ~H - 1~: xuống tới vạch ~0~ là đìa cạn, cá chết; lên tới vạch ~H~ là nước tràn bờ, cá theo nước ra sông hết.

Theo kinh nghiệm của dân miền Tây, con nước thay đổi theo từng giờ, mỗi giờ chỉ có đúng một trong ba khả năng:

  • nước lớn: mực nước tăng ~1~ vạch;
  • nước ròng: mực nước giảm ~1~ vạch;
  • nước đứng: mực nước giữ nguyên.

Một kịch bản con nước trong ~N~ giờ là một dãy gồm ~N~ lựa chọn như trên (giờ thứ nhất, giờ thứ hai, ..., giờ thứ ~N~). Kịch bản được gọi là an toàn nếu sau mỗi giờ (kể cả giờ cuối cùng) mực nước vẫn nằm trong đoạn ~[1, H - 1]~.

Thầy Sơn đang lên kế hoạch cho ~Q~ đợt nuôi khác nhau, đợt nuôi thứ ~i~ bắt đầu khi mực nước ở vạch ~A_i~ và thầy muốn sau đúng ~N~ giờ mực nước ở vạch ~B_i~ (để kịp tháo nước bắt cá). Với mỗi đợt nuôi, hãy giúp thầy Sơn đếm số kịch bản con nước an toàn bắt đầu ở ~A_i~ và kết thúc ở ~B_i~. Vì kết quả có thể rất lớn, chỉ cần in ra phần dư khi chia cho ~10^9 + 7~.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên ~N, H, Q~ ~(1 \le N \le 10^6;~ ~2 \le H \le 10^6;~ ~1 \le Q \le 2 \times 10^5)~.
  • ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~A_i, B_i~ ~(1 \le A_i, B_i \le H - 1)~.
Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là số kịch bản con nước an toàn của đợt nuôi thứ ~i~, lấy theo modulo ~10^9 + 7~.

Giới hạn (Subtask)
  • Subtask 1 (~20\%~ số điểm): ~N, H, Q \le 300~.
  • Subtask 2 (~20\%~ số điểm): ~N \le 5000~ và ~H > N~.
  • Subtask 3 (~30\%~ số điểm): ~H > N~.
  • Subtask 4 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++: 1 giây).

Sample Input 1

3 3 2
1 1
1 2

Sample Output 1

4
4
Giải thích

Mực nước chỉ được là ~1~ hoặc ~2~: ở vạch ~1~ không được nước ròng (cạn đìa), ở vạch ~2~ không được nước lớn (tràn bờ). Hình dưới liệt kê đủ ~8~ kịch bản an toàn bắt đầu ở vạch ~1~: có ~4~ kịch bản kết thúc ở vạch ~1~ và ~4~ kịch bản kết thúc ở vạch ~2~.

Ví dụ 1: tám kịch bản an toàn trong 3 giờ, xuất phát ở vạch 1

Ví dụ 1: tám kịch bản an toàn trong 3 giờ, xuất phát ở vạch 1

Sample Input 2

4 5 3
1 1
2 4
4 1

Sample Output 2

9
9
4
Giải thích
  • Đợt ~1~: có ~9~ kịch bản, chẳng hạn đứng – đứng – đứng – đứng hoặc lớn – ròng – lớn – ròng.
  • Đợt ~2~: kịch bản lớn – đứng – lớn – đứng ~(2 \to 3 \to 3 \to 4 \to 4)~ là an toàn; còn kịch bản lớn – lớn – lớn – ròng ~(2 \to 3 \to 4 \to 5 \to 4)~ tuy cũng kết thúc ở vạch ~4~ nhưng sau giờ thứ ~3~ nước lên tới vạch ~5 = H~ (tràn bờ) nên không an toàn. Tổng cộng có ~9~ kịch bản an toàn.
  • Đợt ~3~: phải giảm ~3~ vạch trong ~4~ giờ nên gồm ~3~ giờ nước ròng và ~1~ giờ nước đứng; giờ nước đứng có ~4~ vị trí để chọn, nên có ~4~ kịch bản.

Ví dụ 2, đợt 2: một kịch bản an toàn và một kịch bản bị tràn bờ

Ví dụ 2, đợt 2: một kịch bản an toàn và một kịch bản bị tràn bờ

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).

Tuyến đua ghe (Đề tự luyện HSG Tin quốc gia #02 – Bài 2)

Nộp bài
Time limit: 1.5 / Memory limit: 256M

Point: 5

⚠️ LƯU Ý: Đây chỉ là cuộc thi thử – các em hãy cố gắng TỰ LỰC làm bài, KHÔNG sử dụng AI, không tra cứu lời giải hay nhờ người khác hỗ trợ, để đánh giá chính xác năng lực thật của bản thân!
🚨 Trong suốt thời gian thi, thầy sẽ LIÊN TỤC KIỂM TRA bài làm của các em. Trường hợp nào bị phát hiện GIAN LẬN sẽ bị XÓA KHỎI CUỘC THI!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Vùng cù lao quê thầy Sơn có ~N~ bến ghe, đánh số từ ~1~ đến ~N~, được nối với nhau bởi ~N - 1~ đoạn kênh. Đoạn kênh thứ ~i~ nối hai bến ~u_i~ và ~v_i~, dài ~w_i~ mét. Từ một bến bất kỳ luôn có thể chèo ghe tới mọi bến khác, và giữa hai bến bất kỳ có đúng một đường đi không quay đầu (nói cách khác, các bến và đoạn kênh tạo thành một cây).

Năm nay thầy Sơn được bà con nhờ chọn tuyến cho hội đua ghe ngo. Một tuyến đua được xác định bởi hai bến khác nhau ~u~ và ~v~: các đội xuất phát ở bến ~u~ và về đích ở bến ~v~ theo đường đi duy nhất giữa chúng (đổi chiều ~u, v~ vẫn là cùng một tuyến). Gọi ~L~ là tổng chiều dài các đoạn kênh trên tuyến và ~D~ là chiều dài đoạn kênh dài nhất trên tuyến.

Kinh nghiệm của thầy Sơn: nếu một đoạn kênh chiếm từ một nửa chiều dài cả tuyến trở lên thì đội nào mạnh nước rút trên đúng đoạn đó gần như chắc thắng, cuộc đua mất hay. Vì vậy thầy gọi một tuyến là cân bằng nếu đoạn dài nhất ngắn hơn hẳn tổng các đoạn còn lại, tức là

~2 \cdot D < L.~

Hãy giúp thầy Sơn đếm xem có bao nhiêu tuyến đua cân bằng.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 2 \times 10^5)~.
  • ~N - 1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le N;~ ~u_i \ne v_i;~ ~1 \le w_i \le 10^9)~. Dữ liệu bảo đảm các đoạn kênh tạo thành một cây.
Kết quả

Một số nguyên duy nhất là số tuyến đua cân bằng (số cặp không thứ tự ~\{u, v\}~, ~u \ne v~, thỏa mãn ~2D < L~).

Giới hạn (Subtask)
  • Subtask 1 (~15\%~ số điểm): ~N \le 2000~.
  • Subtask 2 (~20\%~ số điểm): mọi ~w_i~ bằng nhau.
  • Subtask 3 (~25\%~ số điểm): đoạn kênh thứ ~i~ nối bến ~i~ và bến ~i + 1~ (các bến nằm trên một đường thẳng).
  • Subtask 4 (~40\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++: 1,5 giây).

Sample Input 1

6
1 2 3
2 3 4
3 4 2
2 5 5
5 6 1

Sample Output 1

3
Giải thích

Tuyến có ~1~ hoặc ~2~ đoạn kênh không bao giờ cân bằng. Các tuyến có từ ~3~ đoạn trở lên:

  • ~\{1, 4\}~: các đoạn ~3, 4, 2~, ~L = 9~, ~D = 4~, ~8 < 9~: cân bằng.
  • ~\{4, 5\}~: các đoạn ~2, 4, 5~, ~L = 11~, ~D = 5~, ~10 < 11~: cân bằng.
  • ~\{4, 6\}~: các đoạn ~2, 4, 5, 1~, ~L = 12~, ~D = 5~: cân bằng.
  • ~\{1, 6\}~: các đoạn ~3, 5, 1~, ~L = 9~, ~D = 5~, ~10 \ge 9~: không cân bằng.
  • ~\{3, 6\}~: các đoạn ~4, 5, 1~, ~L = 10~, ~D = 5~, ~10 = 10~: không cân bằng (phải nhỏ hơn hẳn).

Vậy có ~3~ tuyến cân bằng.

Ví dụ 1: bản đồ kênh, tô xanh tuyến giữa bến 4 và bến 6

Ví dụ 1: bản đồ kênh, tô xanh tuyến giữa bến 4 và bến 6

Sample Input 2

5
1 2 2
2 3 3
3 4 4
4 5 1

Sample Output 2

2
Giải thích

Hai tuyến cân bằng là ~\{1, 4\}~ (các đoạn ~2, 3, 4~) và ~\{1, 5\}~ (các đoạn ~2, 3, 4, 1~). Tuyến ~\{2, 5\}~ có các đoạn ~3, 4, 1~ với ~2 \cdot 4 = 8 = L~ nên không cân bằng.

Ví dụ 2: các đoạn kênh trên ba tuyến

Ví dụ 2: các đoạn kênh trên ba tuyến

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).

Điệp khúc (Đề tự luyện HSG Tin quốc gia #02 – Bài 3)

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 5

⚠️ LƯU Ý: Đây chỉ là cuộc thi thử – các em hãy cố gắng TỰ LỰC làm bài, KHÔNG sử dụng AI, không tra cứu lời giải hay nhờ người khác hỗ trợ, để đánh giá chính xác năng lực thật của bản thân!
🚨 Trong suốt thời gian thi, thầy sẽ LIÊN TỤC KIỂM TRA bài làm của các em. Trường hợp nào bị phát hiện GIAN LẬN sẽ bị XÓA KHỎI CUỘC THI!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Tối thứ Bảy, thầy Sơn chèo ghe ra chợ nổi Cái Răng nghe một nhóm đờn ca tài tử biểu diễn ngay trên sông. Thầy ghi lại toàn bộ bản đờn thành một xâu ~S~ gồm ~N~ chữ cái Latin thường, mỗi chữ cái là một nốt nhạc (hò, xự, xang, xê, cống...) được mã hoá thành một chữ.

Nghệ nhân rất thích điệp khúc: một đoạn nhạc được đờn liền hai lần. Tuy nhiên lần đờn thứ hai thường được "luyến láy" thêm cho mùi, nên có thể khác lần đầu ở vài nốt. Cụ thể, một đoạn liên tiếp ~S[s..s+2p-1]~ (độ dài chẵn ~2p \ge 2~) được gọi là một điệp khúc nếu khi chia đôi thành nửa đầu ~X = S[s..s+p-1]~ và nửa sau ~Y = S[s+p..s+2p-1]~ thì số vị trí ~j~ ~(0 \le j < p)~ mà ~X_j \ne Y_j~ không vượt quá ~K~.

Thầy Sơn muốn tìm điệp khúc dài nhất trong bản ghi để đem về dạy học trò. Nếu có nhiều điệp khúc cùng độ dài lớn nhất, thầy chọn điệp khúc có vị trí bắt đầu ~s~ nhỏ nhất.

Hãy giúp thầy Sơn.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 2 \times 10^5,~ ~0 \le K \le 3)~.
  • Dòng thứ hai chứa xâu ~S~ gồm đúng ~N~ chữ cái Latin thường. Các vị trí trong ~S~ được đánh số từ ~1~ đến ~N~.
Kết quả

In ra hai số nguyên: độ dài ~2p~ của điệp khúc dài nhất và vị trí bắt đầu ~s~ nhỏ nhất của một điệp khúc có độ dài đó. Nếu bản ghi không có điệp khúc nào, in ra 0 0.

Giới hạn (Subtask)
  • Subtask 1 (~20\%~ số điểm): ~N \le 300~.
  • Subtask 2 (~30\%~ số điểm): ~N \le 5000~.
  • Subtask 3 (~20\%~ số điểm): ~K = 0~.
  • Subtask 4 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++ là 1 giây).

Sample Input 1

11 1
bcaaabcabbc

Sample Output 1

8 4
Giải thích

Đoạn aabcabbc (bắt đầu ở vị trí ~4~) có nửa đầu aabc, nửa sau abbc, chỉ lệch nhau ~1~ nốt ~\le K = 1~ nên là điệp khúc độ dài ~8~. Hai đoạn độ dài ~10~ là bcaaabcabb (hai nửa bcaaa, bcabb lệch ~2~ nốt) và caaabcabbc (lệch ~3~ nốt) đều không phải điệp khúc.

Ví dụ 1: điệp khúc dài 8 bắt đầu ở vị trí 4

Ví dụ 1: điệp khúc dài 8 bắt đầu ở vị trí 4

Sample Input 2

10 0
baabcabcab

Sample Output 2

6 3
Giải thích

Với ~K = 0~, hai nửa phải giống hệt nhau. Các đoạn abcabc (vị trí ~3~), bcabca (vị trí ~4~), cabcab (vị trí ~5~) đều là điệp khúc độ dài ~6~; thầy Sơn chọn vị trí nhỏ nhất là ~3~. Không có điệp khúc nào dài hơn.

Ví dụ 2: điệp khúc dài 6 bắt đầu ở vị trí 3

Ví dụ 2: điệp khúc dài 6 bắt đầu ở vị trí 3

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).

Chuyến ghe (Đề tự luyện HSG Tin quốc gia #02 – Bài 4)

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 5

⚠️ LƯU Ý: Đây chỉ là cuộc thi thử – các em hãy cố gắng TỰ LỰC làm bài, KHÔNG sử dụng AI, không tra cứu lời giải hay nhờ người khác hỗ trợ, để đánh giá chính xác năng lực thật của bản thân!
🚨 Trong suốt thời gian thi, thầy sẽ LIÊN TỤC KIỂM TRA bài làm của các em. Trường hợp nào bị phát hiện GIAN LẬN sẽ bị XÓA KHỎI CUỘC THI!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Mùa trái cây miền Tây, vựa của thầy Sơn bên bờ kênh Xà No có ~N~ sọt trái cây xếp thành một hàng dọc bến, đánh số từ ~1~ đến ~N~. Sọt thứ ~i~ chứa trái cây loại ~a_i~ (xoài, sầu riêng, chôm chôm, măng cụt...).

Mỗi ngày thầy Sơn nhận ~Q~ đơn hàng giao ra chợ nổi. Đơn hàng thứ ~t~ có dạng ~(l, r, k)~: thầy phải chở tất cả các sọt từ ~l~ đến ~r~ bằng chiếc ghe có đúng ~k~ khoang. Mỗi khoang chỉ được chứa một loại trái cây (nhưng chứa bao nhiêu sọt cùng loại đó cũng được), nên mỗi chuyến ghe chở được các sọt thuộc tối đa ~k~ loại khác nhau. Vì bến hẹp, các sọt phải được bốc lên ghe theo đúng thứ tự ~l, l+1, \ldots, r~: mỗi chuyến ghe chở một đoạn liên tiếp các sọt, chuyến sau tiếp nối ngay chỗ chuyến trước dừng lại.

Với mỗi đơn hàng, hãy giúp thầy Sơn tính số chuyến ghe ít nhất cần dùng. Các đơn hàng độc lập với nhau (sau mỗi đơn, các sọt lại được xếp như cũ).

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 5 \times 10^4)~.
  • Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le N)~.
  • ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~l, r, k~ ~(1 \le l \le r \le N,~ ~1 \le k \le N)~ mô tả một đơn hàng.
Kết quả

Gồm ~Q~ dòng, dòng thứ ~t~ là số chuyến ghe ít nhất cho đơn hàng thứ ~t~.

Giới hạn (Subtask)
  • Subtask 1 (~10\%~ số điểm): ~N, Q \le 1000~.
  • Subtask 2 (~15\%~ số điểm): mọi đơn hàng có cùng một giá trị ~k~.
  • Subtask 3 (~20\%~ số điểm): ~k \le 20~ ở mọi đơn hàng.
  • Subtask 4 (~25\%~ số điểm): ~k \ge 500~ ở mọi đơn hàng.
  • Subtask 5 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++ là 1 giây).

Sample Input 1

9 4
3 3 3 5 5 2 1 4 1
1 9 2
2 6 1
4 9 3
1 9 5

Sample Output 1

3
3
2
1
Giải thích
  • Đơn ~(1, 9, 2)~: có thể chia thành 3 3 3 | 5 5 2 | 1 4 1, mỗi chuyến không quá ~2~ loại. Cả đoạn có ~5~ loại trái cây mà mỗi chuyến chỉ chở được tối đa ~2~ loại, nên không thể dùng ít hơn ~3~ chuyến.
  • Đơn ~(2, 6, 1)~: các sọt 3 3 5 5 2 chia thành 3 3 | 5 5 | 2, cần ~3~ chuyến.
  • Đơn ~(4, 9, 3)~: các sọt 5 2 1 4 1 có ~4~ loại nên một chuyến không đủ; chia thành 5 2 | 1 4 1 là được ~2~ chuyến.
  • Đơn ~(1, 9, 5)~: ghe có ~5~ khoang, đủ cho cả ~5~ loại, nên ~1~ chuyến là đủ.

Ví dụ 1: một cách chia chuyến cho đơn (1, 9, 2) và đơn (4, 9, 3)

Ví dụ 1: một cách chia chuyến cho đơn (1, 9, 2) và đơn (4, 9, 3)

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).