Fişierul intrare/ieşire:stalpisori.in, stalpisori.outSursăAlgoritmiada 2010, Runda Finala
AutorTiberiu SavinAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.45 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Stalpisori

Alexandra este studenta la facultatea de informatica. Astazi, mergand inapoi spre casa a observat ca pe strada pe care merge se afla N stalpisori amplasati pe marginea trotuarului. Fiind studenta la informatica, ea se gandeste imediat la o problema de informatica plecand de la acest lucru. Ea se intreaba care este distanta minima D, astfel incat pentru fiecare din cei N stalpisori, in intervalul [Pi - D, Pi + D] sa se afle cel putin K stalpisori, Pi reprezentand distanta de la inceputul strazii pana la stalpisorul i. Avand in vedere ca Alexandra a picat examenul de algoritmica, ea va roaga pe voi sa o ajutati sa rezolve aceasta problema.

Date de intrare

Fisierul de intrare stalpisori.in contine pe prima linie 2 numere, N si K. Pe urmatoarele N linii urmeaza distantele de la inceputul strazii pana la fiecare stalpisor.

Date de ieşire

Fisierul de iesire stalpisori.out va contine un singur numar reprezentand distanta minima ceruta in enuntul problemei.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ K ≤ N
  • Pozitiile stalpisorilor sunt numere naturale distincte strict mai mici decat 231
  • Pozitiile stalpisorilor vor fi date in ordine crescatoare

Exemplu

stalpisori.instalpisori.out
10 3
5
9
14
20
24
26
35
38
41
43
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content