Nu aveti permisiuni pentru a descarca fisierul grader_test7.in
Diferente pentru problema/stalpisori intre reviziile #1 si #2
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="stalpisori") ==
Poveste şi cerinţă...
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 imedia 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 $[P~i~ - D, P~i~ + D]$ sa se afle cel putin $N$ stalpisori, $P~i~$ 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.
h2. Date de intrare
Fişierul de intrare $stalpisori.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $stalpisori.out$ ...
Fisierul de iesire $stalpisori.out$ va contine un singur numar reprezentand distanta minima ceruta in enuntul problemei.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $ 1 ≤ N ≤ 1.000.000 $ * $ 1 ≤ K ≤ N $ * Pozitiile stalpisorilor sunt numere naturale distincte mai mici decat 2^32^ * Pozitiile stalpisorilor vor fi date in *ordine crescatoare*
h2. Exemplu table(example). |_. stalpisori.in |_. stalpisori.out |
| This is some text written on multiple lines. | This is another text written on multiple lines.
| 10 3 5 9 14 20 24 26 35 38 41 43 | 9
| h3. Explicaţie