Đèn đường chiếu sáng
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Con đường thẳng có độ dài $L$ (từ tọa độ $0$ đến $L$) được đặt $n$ chiếc đèn tại các tọa độ $a_1, a_2, \dots, a_n$. Mỗi chiếc đèn có bán kính chiếu sáng là $d$ (chiếu sáng đoạn $[a_i - d, a_i + d]$). Hãy tìm giá trị nguyên nhỏ nhất của $2d$ (tức đường kính chiếu sáng nhỏ nhất) sao cho toàn bộ con đường $[0, L]$ đều được chiếu sáng.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $n, L$ ($1 \le n \le 1000, 1 \le L \le 10^9$).
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le L$).
Dữ liệu ra
- Một số nguyên duy nhất là giá trị $2d$ nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 7 15 15 5 3 7 9 14 0 |
5 |
Giới hạn
- $1 \le n \le 1000, 1 \le L \le 10^9$
Community Discussion