Nhảy đá qua sông
Points
21
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Một dòng sông có chiều rộng $L$, bờ bên này ở tọa độ $0$ và bờ bên kia ở tọa độ $L$. Giữa sông có $N$ hòn đá nằm tại các tọa độ $d_1 < d_2 < \dots < d_N$ ($0 < d_i < L$). Một chú ếch muốn nhảy từ bờ $0$ sang bờ $L$ bằng cách nhảy qua các hòn đá.
Để thử thách chú ếch, người ta được phép bỏ đi tối đa $M$ hòn đá (không thể bỏ hai bờ $0$ và $L$). Hãy tìm độ dài bước nhảy ngắn nhất lớn nhất có thể mà chú ếch phải thực hiện để đi từ $0$ đến $L$.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $L, N, M$.
- Dòng thứ hai chứa $N$ số nguyên $d_1, d_2, \dots, d_N$.
Dữ liệu ra
In ra độ dài bước nhảy ngắn nhất lớn nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 25 5 2 |
2 11 14 17 21 | 4 | | 10 2 0 3 7 | 3 |
Giới hạn
- $1 \le L \le 10^9$
- $0 \le M \le N \le 10^5$
- $0 < d_1 < d_2 < \dots < d_N < L$.
Community Discussion