Độ khó: Khá (3/4 điểm)

🎓 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

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

Thầy Sơn có ~N~ viên kẹo và muốn làm một thí nghiệm nhỏ với lớp mình. Lần lượt với ~k = 1, 2, \dots, M~, thầy chia đều ~N~ viên kẹo cho ~k~ bạn: mỗi bạn nhận số kẹo như nhau và nhiều nhất có thể, phần kẹo còn dư (đúng bằng ~N \bmod k~) thầy giữ lại cho mình. Kẹo được gom lại trước mỗi lần chia.

Hãy tính tổng số kẹo thầy Sơn giữ lại sau ~M~ lần chia:

~S = \sum_{k=1}^{M} (N \bmod k)~

Vì ~S~ có thể rất lớn, hãy in ra ~S~ chia lấy dư cho ~10^9 + 7~.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên ~N~ và ~M~ ~(1 \le N, M \le 10^{12})~.

Kết quả

Một số nguyên duy nhất là ~S \bmod (10^9 + 7)~.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N, M \le 10^6~.
• Subtask 2 (~40\%~ số điểm): ~M \le N~.
• Subtask 3 (~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à 3 giây.

Sample Input 1

10 15

Sample Output 1

63

Sample Input 2

7 3

Sample Output 2

2

Giải thích

• Ví dụ 1: với ~k = 1, \dots, 10~ phần dư lần lượt là ~0, 0, 1, 2, 0, 4, 3, 2, 1, 0~ (tổng ~13~); với ~k = 11, \dots, 15~ không chia được viên nào cho mỗi bạn nên dư cả ~10~ viên, cộng thêm ~5 \times 10 = 50~. Tổng ~63~.
• Ví dụ 2: ~7 \bmod 1 + 7 \bmod 2 + 7 \bmod 3 = 0 + 1 + 1 = 2~.

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

Độ khó: Khá (3/4 điểm)

🎓 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

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

Dọc một con đường thẳng (xem như trục số) có ~N~ ngôi nhà, nhà thứ ~i~ ở tọa độ ~x_i~, và ~M~ cột điện, cột thứ ~j~ ở tọa độ ~p_j~. Thầy Sơn được nhà mạng nhờ lắp các trạm phát sóng lên tối đa ~K~ cột điện (mỗi cột lắp nhiều nhất một trạm).

Mọi trạm có cùng bán kính phủ sóng ~R~ (~R~ là số nguyên không âm): trạm lắp ở cột tọa độ ~p~ phủ sóng được nhà ở tọa độ ~x~ khi ~|x - p| \le R~. Để tiết kiệm điện, thầy Sơn muốn chọn ~R~ nhỏ nhất sao cho có thể chọn các cột để lắp trạm mà mọi ngôi nhà đều được phủ sóng.

Hãy tìm giá trị ~R~ nhỏ nhất đó.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ ~(1 \le N, M \le 2 \times 10^5;\ 1 \le K \le N)~.
• Dòng thứ hai chứa ~N~ số nguyên ~x_1, x_2, \dots, x_N~.
• Dòng thứ ba chứa ~M~ số nguyên ~p_1, p_2, \dots, p_M~.

Mọi tọa độ đều là số nguyên có giá trị tuyệt đối không quá ~10^9~. Các nhà, các cột có thể trùng tọa độ với nhau và không nhất thiết được cho theo thứ tự.

Kết quả

Một số nguyên duy nhất là bán kính ~R~ nhỏ nhất.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N, M \le 300~ và mọi tọa độ có giá trị tuyệt đối không quá ~300~.
• Subtask 2 (~20\%~ số điểm): ~K = 1~.
• Subtask 3 (~60\%~ 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

5 4 2
1 5 9 14 20
3 8 12 18

Sample Output 1

6

Giải thích

Với ~R = 6~, lắp trạm ở cột ~3~ (phủ đoạn ~[-3, 9]~, gồm các nhà ~1, 5, 9~) và cột ~18~ (phủ đoạn ~[12, 24]~, gồm các nhà ~14, 20~). Với ~R = 5~ thì cần ít nhất ~3~ trạm.

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

Độ khó: Khá (3/4 điểm)

🎓 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

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

Trường THPT Hoa Sen tổ chức phong trào thi đua giữa ~N~ lớp, đánh số từ ~1~ đến ~N~. Ban đầu lớp thứ ~i~ có ~a_i~ điểm thi đua. Trong suốt học kì có ~Q~ sự kiện xảy ra lần lượt, mỗi sự kiện thuộc một trong ba loại:

• 1 i x: lớp ~i~ được cộng thêm ~x~ điểm.
• 2 i: thầy Sơn (tổng phụ trách) hỏi thứ hạng hiện tại của lớp ~i~, được tính bằng ~1~ cộng với số lớp có điểm lớn hơn hẳn điểm của lớp ~i~ (các lớp bằng điểm nhau có cùng thứ hạng).
• 3 k: thầy Sơn hỏi điểm của lớp đứng ở vị trí thứ ~k~ khi xếp tất cả các lớp theo điểm giảm dần (các lớp bằng điểm vẫn chiếm các vị trí khác nhau).

Hãy trả lời tất cả các câu hỏi.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(0 \le a_i \le 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng ở trên, với ~1 \le i \le N~, ~1 \le x \le 10^9~, ~1 \le k \le N~.

Kết quả

Với mỗi sự kiện loại ~2~ hoặc ~3~, in ra câu trả lời trên một dòng.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N, Q \le 5000~.
• Subtask 2 (~30\%~ số điểm): điểm của mọi lớp ở mọi thời điểm đều không vượt quá ~10^6~.
• Subtask 3 (~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à 3 giây.

Sample Input 1

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

Sample Output 1

2
8
1
8
4
8

Giải thích

Ban đầu điểm là ~(5, 8, 5, 2)~: lớp ~1~ có một lớp hơn điểm nên đứng hạng ~2~; lớp cao điểm nhất có ~8~ điểm. Sau khi lớp ~4~ được cộng ~6~ điểm, điểm là ~(5, 8, 5, 8)~: lớp ~4~ đứng hạng ~1~ (bằng điểm lớp ~2~), và khi xếp giảm dần ~8, 8, 5, 5~ thì vị trí thứ ~2~ có ~8~ điểm. Sau khi lớp ~1~ được cộng ~4~ điểm, điểm là ~(9, 8, 5, 8)~: lớp ~3~ có ba lớp hơn điểm nên đứng hạng ~4~; dãy giảm dần là ~9, 8, 8, 5~ nên vị trí thứ ~3~ có ~8~ điểm.

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

Độ khó: Khó (4/4 điểm)

🎓 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

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

Vùng sông nước có ~N~ bến, đánh số từ ~1~ đến ~N~, và ~M~ tuyến đường hai chiều nối các bến. Tuyến thứ ~i~ nối hai bến ~u_i, v_i~ và đi hết ~w_i~ phút. Có hai loại tuyến:

• Nếu ~p_i = 0~: đây là đường bộ, có thể xuất phát bất cứ lúc nào.
• Nếu ~p_i > 0~: đây là tuyến phà. Phà (theo cả hai chiều) chỉ rời bến vào các thời điểm ~0, p_i, 2p_i, 3p_i, \dots~ Nếu đến bến lúc ~t~ mà muốn đi phà thì phải chờ tới thời điểm rời bến sớm nhất không nhỏ hơn ~t~.

Thầy Sơn xuất phát từ bến ~1~ ở thời điểm ~0~ và cần tới bến ~N~ càng sớm càng tốt. Thầy Sơn có ~K~ vé ưu tiên: khi dùng một vé cho một lần đi phà, phà rời bến ngay lúc thầy Sơn tới (không phải chờ). Mỗi vé chỉ dùng được một lần. Thầy Sơn được phép đi qua một bến hay một tuyến nhiều lần.

Hãy tính thời điểm sớm nhất thầy Sơn tới được bến ~N~.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ ~(2 \le N \le 10^5;\ 1 \le M \le 2 \times 10^5;\ 0 \le K \le 5)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên ~u_i, v_i, w_i, p_i~ ~(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 1 \le w_i \le 10^9;\ 0 \le p_i \le 10^9)~. Giữa hai bến có thể có nhiều tuyến.

Kết quả

Một số nguyên duy nhất là thời điểm sớm nhất tới bến ~N~. Nếu không thể tới được, in ra -1.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): mọi ~p_i = 0~.
• Subtask 2 (~30\%~ số điểm): ~K = 0~.
• 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à 5 giây.

Sample Input 1

4 4 0
1 2 2 0
2 4 3 4
1 3 1 0
3 4 7 0

Sample Output 1

7

Sample Input 2

4 4 1
1 2 2 0
2 4 3 4
1 3 1 0
3 4 7 0

Sample Output 2

5

Giải thích

• Ví dụ 1: đi bộ ~1 \to 2~ tới lúc ~2~, chờ phà ~2 \to 4~ rời bến lúc ~4~, tới bến ~4~ lúc ~7~. Đi đường ~1 \to 3 \to 4~ cũng tới lúc ~1 + 7 = 8~, chậm hơn.
• Ví dụ 2: tới bến ~2~ lúc ~2~ thì dùng vé ưu tiên, phà rời bến ngay, tới bến ~4~ lúc ~5~.

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

Độ khó: Khó (4/4 điểm)

🎓 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

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

Cuối năm học, thầy Sơn tổ chức giải đấu lập trình đồng đội cho lớp. ~N~ học sinh đã xếp thành một hàng dọc, học sinh thứ ~i~ (tính từ đầu hàng) có điểm năng lực là ~a_i~.

Để các đội được thành lập nhanh chóng, thầy Sơn quy định: không ai được đổi chỗ trong hàng, thầy chỉ "cắt" hàng thành các đoạn liên tiếp, mỗi đoạn là một đội. Mỗi học sinh thuộc đúng một đội, và mỗi đội phải có ít nhất ~L~ và nhiều nhất ~R~ học sinh.

Thầy Sơn muốn các thành viên trong một đội có năng lực sát nhau để làm việc ăn ý. Độ lệch của một đội là hiệu giữa điểm năng lực lớn nhất và nhỏ nhất của các thành viên trong đội đó (đội mà mọi người bằng điểm nhau thì có độ lệch ~0~).

Hãy giúp thầy Sơn chia hàng thành các đội sao cho tổng độ lệch của tất cả các đội là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~N, L, R~ ~(1 \le L \le R \le N \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~.

Kết quả

Một số nguyên duy nhất là tổng độ lệch nhỏ nhất. Nếu không có cách chia nào thỏa mãn, in ra -1.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 200~.
• 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à 5 giây.

Sample Input 1

8 2 4
7 3 1 2 7 9 5 4

Sample Output 1

8

Sample Input 2

9 2 3
2 8 8 8 8 5 2 3 2

Sample Output 2

10

Sample Input 3

5 3 4
1 2 3 4 5

Sample Output 3

-1

Giải thích

• Ví dụ 1: chia thành ~4~ đội ~[7, 3], [1, 2], [7, 9], [5, 4]~ với độ lệch lần lượt ~4, 1, 2, 1~, tổng bằng ~8~.
• Ví dụ 2: một cách chia tối ưu là ~[2, 8, 8], [8, 8, 5], [2, 3, 2]~ với tổng độ lệch ~6 + 3 + 1 = 10~.
• Ví dụ 3: mỗi đội có ~3~ hoặc ~4~ học sinh nên ~5~ học sinh không thể chia thành 1 đội (quá đông) hay từ 2 đội trở lên (thiếu người).

Nguồn: Đề tự luyện HSG Tin học lớp 12 do thầy Nguyễn Việt Nam Sơn biên soạn (đề tự soạn).