- Mã:
- Golden_Island
- Tên:
- Đào vàng
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4601103044
Đào vàng là trò chơi khá phổ biến và có nhiều phiên bản. Hãy cùng xét một phiên bản của trò chơi này. Có N thỏi vàng được cố định ở các vị trí X1, X2, X3, ..., Xn trên một trục nằm ngang. Nếu người chơi đào ở vị trí X với máy khoan có lực đập R thì có thể lấy được các thỏi vàng cách vị trí X tối đa R đơn vị chiều dài hay các thỏi vàng có vị trí nằm trong khoảng [X - R;X + R]. Người chơi được đào tối đa K lần và lực đập R là giống nhau ở các lần đào. Nếu người chơi chọn lực đập R càng nhỏ thì số điểm đạt được càng cao và ngược lại. Người chơi được thực hiện tối đa K lần đào, hãy giúp người chơi chọn lực đập R nhỏ nhất để có thể đào hết N thỏi vàng.
Yêu cầu: Cho trước vị trí của N thỏi hàng, hãy viết chương trình tìm giá trị nguyên R bé nhất sao cho người chơi có thể lấy được N thỏi vàng sau tối đa K lần đào.
Dòng đầu chứa 2 số nguyên N và K lần lượt cho biết số lượng thỏi vàng và số lần đào tối đa. Dòng thứ i trong N dòng tiếp theo cho biết vị trí Xi (0 ≤ Xi ≤ 109) của thỏi vàng thứ i.
Một số nguyên là giá trị lực đập R bé nhất để lấy được N thỏi vàng tối đa sau K lần đào.
Input
Output
6 1
2
20
6
5
4
17
9
Input
Output
6 2
2
20
6
5
4
17
2
Theme :
Mời bạn soạn code