copaci3

Copaci 3

== include(page="template/taskheader" task_id="copaci3") ==

Poveste şi cerinţă...

Badea Ion si-a cumparat de curand un teren pe care a plantat niste pomi. Obosit, insa satisfacut dupa o zi intreaga de plantat pomi, Badea Ion s-a asezat frumos pe prispa sa isi admire munca. Stand acolo si uitandu-se la pomi, el observa ca pomii lui sunt foarte inestetici. Pentru asta, se gandeste sa imprumute bagheta magica pe care o foloseste Badea Gheorghe pentru a mari, respectiv a micsora lucruri pentru a isi infrumuseta pomi. Pomii au fost plantati in linie si fiecare pom are o inaltime de $X{~i~}$ metri. Badea Ion considera ca pomii sunt estetici daca si numai daca nu exista doi pomi consecutivi intre care diferenta de inaltime sa fie mai mare decat $D$. Folosind bagheta magica, el poate sa micsoreze sau sa mareasca inaltimea unui pom cu $1$ metru printr-o singura atingere. De asemenea, primul si ultimul pom au fost plantati de nepotii lui Badea Ion si nu vrea ca acestia sa fie modificati.
 
h2. Cerinta
 
Fiind obosit atat din punct de vedere fizic cat si psihic, Badea Ion va cere ajutorul si va intreaba care este numarul minim de atingeri necesare pentru ca pomii sa indeplineasca conditia de mai sus.

h2. Date de intrare

Fişierul de intrare $copaci3.in$ ...

Pe prima linie a fisierului $copaci3.in$ se afla $2$ numere, $N$ si $D$, reprezentand numarul de pomi, respectiv diferenta maxima de inaltime dintre $2$ pomi pentru ca acestia sa nu fie inestetici. Pe urmatoarea linie se dau in ordine inaltimile celor $N$ pomi.

h2. Date de ieşire

În fişierul de ieşire $copaci3.out$ ...

In fisierul $copaci3.out$ se va afisa un singur numar reprezentand numarul minim de atingeri cu bagheta pe care trebuie sa le efectueze Badea Ion.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100$
* $0 ≤ D ≤ 10^9^$
* $0 ≤ X{~i~} ≤ 10^9^$
* In caz ca nu se poate ajunge la o configuratie estetica se va afisa -1
* Badea Ion va recomanda sa folositi numere intregi pe 64 de biti pentru a calcula rezultatul

h2. Exemplu
table(example). |_. copaci3.in |_. copaci3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 2
1 5 1 4
| 3

|
h3. Explicaţie

...

Pomul $2$ este micsorat cu $2$ metri, iar pomul $3$ este marit cu $1$ metru.

== include(page="template/taskfooter" task_id="copaci3") ==

4084