Fişierul intrare/ieşire:copaci3.in, copaci3.outSursăSummer Challenge 2009, Runda 3
AutorDin FolclorAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Copaci3

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 Xi 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.

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.

Date de intrare

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.

Date de ieşire

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.

Restricţii

  • 1 ≤ N ≤ 100
  • 0 ≤ D ≤ 109
  • 0 ≤ Xi ≤ 109
  • 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

Exemplu

copaci3.incopaci3.out
4 2
1 5 1 4
3

Explicaţie

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content