Độ 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).