E. Wi-Fi minoralar

Qishloqning bosh ko‘chasi to‘g‘ri chiziqdan iborat. Ko‘chada n ta uy bor, i-uy xᵢ nuqtada joylashgan (barcha nuqtalar turlicha).

Internet provayderi k ta uyning tomiga Wi-Fi minora o‘rnatmoqchi (bitta uyga ko‘pi bilan bitta minora). Minoralar bir-biriga xalaqit bermasligi uchun eng yaqin ikki minora orasidagi masofa iloji boricha katta bo‘lishi kerak. Shu masofaning eng katta mumkin bo‘lgan qiymatini toping.

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son — n va k.
Ikkinchi qatorda n ta butun son — x₁, x₂, …, xₙ (tartiblanmagan bo‘lishi mumkin).

Chiqish ma’lumotlari

Bitta son — eng yaqin ikki minora orasidagi masofaning eng katta qiymati.

Cheklovlar

2 ≤ k ≤ n ≤ 5·10⁴; 0 ≤ xᵢ ≤ 10⁹; barcha xᵢ turlicha.

1–70-testlar 1 balldan, 71–80-testlar 3 balldan, jami 100 ball. 1–2-testlar — shartdagi misollar.

1-misol: minoralarni 1, 4, 8 (yoki 1, 4, 9) nuqtalarga qo‘yish mumkin, eng kichik oraliq 3. Masofani 4 yoki undan katta qilib 3 ta minora qo‘yib bo‘lmaydi.

2-misol: barcha 4 ta uyga minora qo‘yiladi: 0, 10, 20, 30 — javob 10.