LINECITY - Mua nhà yên tĩnh

View as PDF

Submit solution

Points: 100.00
Time limit: 1.0s
Memory limit: 1000M
Input: stdin
Output: stdout

Author:
Problem types
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Quang đang dự định mua một ngôi nhà mới tại Linecity. Thành phố Linecity nằm trên hệ trục tọa độ Ox. Có tổng cộng L+1 ngôi nhà trong thành phố được đánh số từ 0 đến L, ngôi nhà thứ i có tọa độ i. Trong đó, có N ngôi nhà đã được mua.

Do là một người trầm tính và yêu thích không gian yên tĩnh, Quang đánh giá rằng độ yên tĩnh của ngôi nhà thứ i là khoảng cách nhỏ nhất từ nó đến một ngôi nhà bất kì khác mà đã được mua. Nói cách khác, độ yên tĩnh của ngôi nhà thứ imin(|ij|) với mọi j sao cho 0jL và ngôi nhà j đã được mua. Hãy giúp Quang tìm mua nhà sao cho độ yên tĩnh của ngôi nhà được mua là lớn nhất có thể.

Dữ liệu
  • Dòng đầu tiên gồm hai số nguyên LN (1L109,1Nmin(L,105)) - số ngôi nhà và số ngôi nhà đã được mua.
  • Dòng thứ hai gồm một dãy N số nguyên A1,A2,...,AN(0AiL) - cho biết tọa độ của các ngôi nhà đã được mua. Dữ liệu vào đảm bảo Không có hai số nào trong dãy trùng nhau.
Kết quả
  • In ra độ yên tĩnh lớn nhất của ngôi nhà mua được.
Chấm điểm
  • Subtask 1 (50% số điểm): L105,N100
  • Subtask 2 (50% số điểm): Không có ràng buộc gì thêm
Ví dụ
Sample Input 1
Copy
12 4
2 5 6 12
Sample Output 1
Copy
3
Sample Input 2
Copy
10 4 
0 2 3 4
Sample Output 2
Copy
6
Giải thích
  • Trong ví dụ thứ nhất, ta chọn mua ngôi nhà thứ 9 với độ yên tĩnh là 3.
  • Trong ví dụ thứ hai, ta chọn mua ngôi nhà thứ 10 với độ yên tĩnh là 6.

Nguồn: Free Contest


Comments

Please read the guidelines before commenting.