Tối ưu hóa trạm gác trên đường tròn
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ ngôi nhà nằm trên một con đường khép kín dạng đường tròn có chu vi $L$. Ngôi nhà thứ $i$ nằm ở vị trí $p_i$ ($0 \le p_1 < p_2 < \dots < p_N < L$). Ta cần đặt $K$ trạm gác cùng bán kính phủ sóng $R$ tại các vị trí bất kỳ trên đường tròn sao cho mọi ngôi nhà đều nằm trong phạm vi phủ sóng của ít nhất một trạm (khoảng cách theo cung tròn ngắn hơn $\le R$).
Để tránh sử dụng số thực, hãy tìm giá trị nguyên nhỏ nhất của đường kính phủ sóng $D = 2R$ thỏa mãn yêu cầu.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, K, L$ ($1 \le K \le N \le 400$, $1 \le L \le 10^9$).
- Dòng thứ hai chứa $N$ số nguyên tăng dần $p_1, p_2, \dots, p_N$ ($0 \le p_i < L$).
Dữ liệu ra
- In ra giá trị nguyên nhỏ nhất của $D = 2R$.
Ví dụ
| Input | Output |
|---|---|
| 5 2 10 0 2 5 6 9 |
3 |
Giới hạn
- $1 \le K \le N \le 400$
- $1 \le L \le 10^9$
Community Discussion