Thi thử HSG Tin 9 #02 – 30/10/2026 (Công khai cho mọi người)

Sơn cọc tiêu (Đề tự luyện HSG Tin 9 #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

Dọc bờ kênh xáng trước trường, xã cắm một hàng cọc tiêu rất dài, các cọc được đánh số lần lượt ~1, 2, 3, \dots~ (coi như hàng cọc dài vô tận). Nhân dịp làm công trình thanh niên, thầy Sơn chia học trò thành ba nhóm, mỗi nhóm cầm một màu sơn:

  • Nhóm Đỏ sơn mọi cọc có số thứ tự chia hết cho ~a~;
  • Nhóm Vàng sơn mọi cọc có số thứ tự chia hết cho ~b~;
  • Nhóm Xanh sơn mọi cọc có số thứ tự chia hết cho ~c~.

Một cọc được đúng một nhóm sơn thì có màu tươi, rất đẹp. Một cọc bị từ hai nhóm trở lên sơn chồng lên nhau thì màu bị lem, phải cạo ra sơn lại; còn cọc không nhóm nào sơn thì vẫn giữ màu xi măng.

Thầy Sơn muốn chụp ảnh các đoạn bờ kênh để làm kỷ yếu, nên thầy hỏi ~Q~ câu: với đoạn từ cọc số ~L~ đến cọc số ~R~ (tính cả hai đầu), có bao nhiêu cọc màu tươi (được đúng một nhóm sơn)?

Hãy giúp thầy Sơn trả lời tất cả các câu hỏi.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên ~a, b, c~ ~(1 \le a, b, c \le 10^{18})~. Ba số này có thể bằng nhau.
  • Dòng thứ hai chứa số nguyên ~Q~ ~(1 \le Q \le 10^5)~.
  • ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ ~(1 \le L \le R \le 10^{18})~ mô tả một câu hỏi.
Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là số cọc màu tươi trong đoạn của câu hỏi thứ ~i~.

Giới hạn (Subtask)
  • Subtask 1 (~20\%~ số điểm): ~Q \le 10~ và ~R \le 10^6~ ở mọi câu hỏi.
  • Subtask 2 (~30\%~ số điểm): ~R \le 10^6~ ở mọi câu hỏi.
  • Subtask 3 (~50\%~ 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à 3 giây.

Sample Input 1

2 3 5
2
1 10
11 29

Sample Output 1

6
8
Giải thích

Câu hỏi 1, đoạn cọc ~1 \dots 10~: các cọc màu tươi là ~2, 3, 4, 5, 8, 9~; cọc ~6~ và cọc ~10~ bị lem, cọc ~1~ và cọc ~7~ không nhóm nào sơn. Vậy có ~6~ cọc màu tươi.

Câu hỏi 2, đoạn cọc ~11 \dots 29~: các cọc màu tươi là ~14, 16, 21, 22, 25, 26, 27, 28~, tức là ~8~ cọc.

Ví dụ 1: màu của từng cọc trong hai đoạn được hỏi

Ví dụ 1: màu của từng cọc trong hai đoạn được hỏi

Sample Input 2

9 9 6
1
2 17

Sample Output 2

2
Giải thích

Cọc ~9~ được cả nhóm Đỏ và nhóm Vàng sơn nên bị lem. Trong đoạn từ cọc ~2~ đến cọc ~17~ chỉ có cọc ~6~ và cọc ~12~ là màu tươi.

Ví dụ 2: màu của các cọc từ 1 đến 18 (đoạn được hỏi là 2 đến 17)

Ví dụ 2: màu của các cọc từ 1 đến 18 (đoạn được hỏi là 2 đến 17)

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).

Vòng cù lao (Đề tự luyện HSG Tin 9 #02 – Bài 2)

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

Giữa dòng sông Hậu có một cù lao, quanh cù lao có ~N~ nhà học trò của thầy Sơn, mỗi nhà có một bến xuồng. Các bến xếp thành một vòng tròn và được đánh số ~1, 2, \dots, N~ theo chiều nước chảy: từ bến ~i~ chèo xuôi sẽ tới bến ~i + 1~, còn từ bến ~N~ chèo xuôi sẽ quay về bến ~1~.

Dịp đầu năm học, thầy Sơn chèo xuồng đi thăm nhà học trò. Thầy chọn một bến xuất phát ~s~, rồi ghé lần lượt các nhà ~s, s + 1, s + 2, \dots~ theo chiều nước chảy (đi qua bến ~N~ thì tiếp tục với bến ~1~), không bỏ qua nhà nào và không ghé nhà nào hai lần (nên ghé tối đa ~N~ nhà). Ghé nhà thứ ~i~ mất ~a_i~ phút (tính luôn thời gian chèo tới bến kế tiếp); có nhà ~a_i = 0~ vì nhà vắng người, thầy chỉ treo quà ở cổng rồi đi ngay.

Thầy chỉ có ~T~ phút, nên tổng thời gian của các nhà được ghé không được vượt quá ~T~. Hãy giúp thầy Sơn tính:

  • ~K~ là số nhà nhiều nhất thầy có thể ghé thăm (khi chọn bến xuất phát tốt nhất);
  • ~C~ là số bến xuất phát ~s~ (~1 \le s \le N~) mà nếu xuất phát từ ~s~ thì thầy ghé được đúng ~K~ nhà.

Nếu thầy không thể ghé được nhà nào (tức ~K = 0~), quy ước ~C = 0~.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên ~N~ và ~T~ ~(1 \le N \le 2 \times 10^5;~ ~0 \le T \le 10^{18})~.
  • Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(0 \le a_i \le 10^9)~.
Kết quả

In ra hai số nguyên ~K~ và ~C~, cách nhau một dấu cách.

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 (~50\%~ 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à 3 giây.

Sample Input 1

6 12
3 6 2 7 2 9

Sample Output 1

3 2
Giải thích
  • Xuất phát từ bến ~1~: ghé nhà ~1, 2, 3~ hết ~3 + 6 + 2 = 11~ phút (thêm nhà ~4~ thì thành ~18 > 12~) → ~3~ nhà.
  • Xuất phát từ bến ~2~: ghé nhà ~2, 3~ hết ~8~ phút (thêm nhà ~4~ thì thành ~15~) → ~2~ nhà.
  • Xuất phát từ bến ~3~: ghé nhà ~3, 4, 5~ hết ~2 + 7 + 2 = 11~ phút (thêm nhà ~6~ thì thành ~20~) → ~3~ nhà.
  • Xuất phát từ bến ~4~: ghé nhà ~4, 5~ hết ~9~ phút (thêm nhà ~6~ thì thành ~18~) → ~2~ nhà.
  • Xuất phát từ bến ~5~: ghé nhà ~5, 6~ hết ~11~ phút (thêm nhà ~1~ thì thành ~14~) → ~2~ nhà.
  • Xuất phát từ bến ~6~: ghé nhà ~6~ rồi nhà ~1~, hết ~9 + 3 = 12~ phút (thêm nhà ~2~ thì thành ~18~) → ~2~ nhà.

Vậy ~K = 3~ và có ~C = 2~ bến xuất phát (bến ~1~ và bến ~3~) đạt được ~3~ nhà.

Ví dụ 1: sáu bến quanh cù lao và một số chuyến đi

Ví dụ 1: sáu bến quanh cù lao và một số chuyến đi

Sample Input 2

6 6
0 5 0 4 7 2

Sample Output 2

3 1
Giải thích

Nhà ~1~ và nhà ~3~ vắng người nên ghé mất ~0~ phút. Xuất phát từ bến ~1~, thầy ghé nhà ~1, 2, 3~ hết ~0 + 5 + 0 = 5~ phút (thêm nhà ~4~ thì thành ~9 > 6~) → ~3~ nhà. Xuất phát từ các bến ~2, 3, 4, 5, 6~ thì ghé được lần lượt ~2, 2, 1, 0, 2~ nhà (riêng bến ~5~: nhà ~5~ đã mất ~7 > 6~ phút nên không ghé được nhà nào). Vậy ~K = 3~ và ~C = 1~.

Ví dụ 2: có nhà vắng người (0 phút)

Ví dụ 2: có nhà vắng người (0 phút)

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).

Tưới vườn cam (Đề tự luyện HSG Tin 9 #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

Vườn cam sành của thầy Sơn ở Tam Bình (Vĩnh Long) được trồng thẳng hàng thành một lưới gồm ~M~ hàng và ~N~ cột; cây ở hàng ~r~, cột ~c~ gọi là cây ~(r, c)~ ~(1 \le r \le M,~ ~1 \le c \le N)~.

Mùa nắng, thầy Sơn kéo máy bơm tưới vườn ~P~ lần. Lần tưới thứ ~i~ phủ nước lên mọi cây trong một khu hình chữ nhật, được thầy ghi lại bằng hai góc đối diện ~(r_1, c_1)~ và ~(r_2, c_2)~ của khu đó. Vì thầy ghi vội nên hai góc có thể là góc trên-trái và dưới-phải, cũng có thể là góc dưới-phải và trên-trái, hay góc trên-phải và dưới-trái... (không đảm bảo ~r_1 \le r_2~ hay ~c_1 \le c_2~). Hai khu tưới có thể chồng lên nhau; mỗi lần tưới thì mỗi cây trong khu nhận thêm ~1~ lượt nước.

Một cây được gọi là đủ nước nếu sau cả ~P~ lần tưới nó nhận được ít nhất ~K~ lượt nước.

Để chuẩn bị bán cam, thầy Sơn hỏi ~Q~ câu: trong khu hình chữ nhật có hai góc đối diện ~(x_1, y_1)~ và ~(x_2, y_2)~ (cũng không đảm bảo thứ tự), có bao nhiêu cây đủ nước?

Hãy giúp thầy Sơn trả lời tất cả các câu hỏi.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên ~M, N, K~ ~(1 \le M, N;~ ~M \times N \le 10^6;~ ~0 \le K \le 10^5)~.
  • Dòng thứ hai chứa số nguyên ~P~ ~(1 \le P \le 10^5)~.
  • ~P~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~r_1, c_1, r_2, c_2~ ~(1 \le r_1, r_2 \le M;~ ~1 \le c_1, c_2 \le N)~ mô tả một lần tưới.
  • Dòng tiếp theo chứa số nguyên ~Q~ ~(1 \le Q \le 10^5)~.
  • ~Q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x_1, y_1, x_2, y_2~ ~(1 \le x_1, x_2 \le M;~ ~1 \le y_1, y_2 \le N)~ mô tả một câu hỏi.
Kết quả

Gồm ~Q~ dòng, dòng thứ ~j~ là số cây đủ nước trong khu của câu hỏi thứ ~j~.

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

Lưu ý: chỉ có ~M \times N \le 10^6~, nên vườn có thể rất "dài" như ~M = 1, N = 10^6~ hoặc ~M = 10^6, N = 1~.

💡 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à 4 giây.

Sample Input 1

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

Sample Output 1

3
2
Giải thích

Số lượt nước của từng cây sau ba lần tưới:

1 1 1 0
2 2 2 1
0 1 1 1

Các cây đủ nước (ít nhất ~2~ lượt) là ~(2, 1), (2, 2), (2, 3)~. Câu hỏi 1 hỏi cả vườn nên đáp án là ~3~. Câu hỏi 2 hỏi khu hàng ~1..3~, cột ~2..3~, chứa hai cây đủ nước ~(2, 2), (2, 3)~.

Ví dụ 1: ba lần tưới (vòng đen là hai góc được ghi)

Ví dụ 1: ba lần tưới (vòng đen là hai góc được ghi)

Ví dụ 1: số lượt nước của từng cây và hai khu được hỏi

Ví dụ 1: số lượt nước của từng cây và hai khu được hỏi

Sample Input 2

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

Sample Output 2

4
Giải thích

Với ~K = 0~, mọi cây đều đủ nước (kể cả cây chưa được tưới lần nào), nên khu hàng ~1..2~, cột ~2..3~ có ~4~ cây đủ nước.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).

Chuyến du khảo (Đề tự luyện HSG Tin 9 #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

Cuối học kỳ, thầy Sơn thuê một chiếc ghe chở học trò đi du khảo trên kênh Xà No. Con kênh được chia thành ~N~ khúc liên tiếp, đánh số từ ~1~ đến ~N~ theo chiều ghe chạy. Khúc thứ ~i~ có độ vui ~a_i~: khúc có vườn cây trái, chợ quê thì ~a_i > 0~; khúc nắng gắt, nước đục, nhiều lục bình thì ~a_i~ có thể âm (học trò thấy mệt và chán).

Thầy Sơn chọn một đoạn khúc liên tiếp ~l, l + 1, \dots, r~ ~(1 \le l \le r \le N)~ để ghe chạy qua. Để học trò đỡ mệt, thầy được phép cho cả lớp ngủ trưa ở một số khúc trong đoạn đã chọn: khi ngủ ở khúc ~i~, cả lớp không thấy gì nên khúc đó được tính độ vui bằng ~0~ (thay cho ~a_i~). Tuy nhiên:

  • cả chuyến đi chỉ được ngủ ở tối đa ~K~ khúc;
  • không được ngủ ở hai khúc liên tiếp (ngủ dậy thì phải thức ngắm cảnh ít nhất một khúc rồi mới được ngủ tiếp).

Tổng độ vui của chuyến đi là tổng ~a_i~ của các khúc mà cả lớp thức trong đoạn đã chọn. Hãy giúp thầy Sơn chọn đoạn kênh và các khúc ngủ sao cho tổng độ vui là lớn nhất.

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 10)~.
  • Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(|a_i| \le 10^9)~.
Kết quả

Một số nguyên duy nhất là tổng độ vui lớn nhất có thể đạt được. Lưu ý đoạn kênh được chọn phải có ít nhất một khúc.

Giới hạn (Subtask)
  • Subtask 1 (~20\%~ số điểm): ~N \le 15~.
  • Subtask 2 (~30\%~ số điểm): ~N \le 3000~ và ~K \ge 1~.
  • Subtask 3 (~50\%~ 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à 3 giây.

Sample Input 1

9 2
9 7 -3 7 -8 -2 8 5 -1

Sample Output 1

34
Giải thích

Thầy chọn đoạn từ khúc ~1~ đến khúc ~8~ và cho cả lớp ngủ ở khúc ~3~ và khúc ~5~: tổng độ vui là ~9 + 7 + 0 + 7 + 0 + (-2) + 8 + 5 = 34~.

Ví dụ 1: độ vui từng khúc và chuyến đi tốt nhất

Ví dụ 1: độ vui từng khúc và chuyến đi tốt nhất

Sample Input 2

4 0
-5 -2 -7 -3

Sample Output 2

-2
Giải thích

Không được ngủ khúc nào (~K = 0~) mà khúc nào cũng có độ vui âm, nên thầy chọn đoạn chỉ gồm một khúc ~2~ có độ vui ~-2~.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).