Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | stalpisori.in, stalpisori.out | Sursă | Algoritmiada 2010, Runda Finala |
| Autor | Tiberiu Savin | Adăugată de |  Savin Tiberiu •devilkind |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Stalpisori
 In momentul in care trimiti o sursa, vei putea vedea scorul obtinut pe o parte din testele folosite la evaluare in monitor. |
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.in | stalpisori.out |
|---|---|
| 10 3 5 9 14 20 24 26 35 38 41 43 | 9 |
