Problema efort, Campion 2009

Un biciclist vrea sa realizeze turul Romaniei. Pentru acest lucru isi stabileste traseul si n orase unde poate sa faca cate un popas ca sa se odihneasca. Ultimul oras este punctul de sosire. Pentru fiecare oras se cunoaste distanta in kilometri de la orasul anterior la acesta, notate cu d1, d2, …, dn.
d1 este distanta de la punctul de plecare la primul oras, d2 este distanta de la primul oras la al doilea, …, dn este distanta de la penultimul oras la ultimul.
Efortul depus pentru deplasare este masurat in picaturi de transpiratie. Astfel dupa fiecare kilometru parcurs pe primii k kilometri de la ultimul popas pierde cate o picatura de transpiratie, iar apoi numarul acestora devine la fiecare kilometru egal cu suma picaturilor de la ultimii doi kilometri parcursi anterior.
Biciclistul opreste de fiecare data la primul popas posibil, dar numai dupa ce strabate cel putin k kilometri (de la popasul anterior).

Cerinta

Sa se scrie un program care determina efortul depus de biciclist (numarul total de picaturi de transpiratie) pentru realizarea turului Romaniei.

Date de intrare

Fisierul de intrare efort.in are pe prima linie numerele n si k separate printr-un spatiu, iar pe linia a doua n numere naturale reprezentand distantele d1, d2, …, dn separate intre ele prin cate un spatiu.

Date de iesire

Fisierul de iesire efort.out va contine o singura linie pe care se va afisa un numar natural reprezentand efortul depus de biciclist.

Restrictii

• 0 < k, n < 1001
• 0 < d1, d2, ..., dn < 201
• Pentru toate testele efortul depus de biciclist este < 2000000000.

Exemple

efort.in	efort.out	Explicatie
4 10 5 9 7 5	43	Primul popas este la al doilea oras, pana la care efortul este 28, apoi nu mai poate face popas decat la sosire, pana acolo efortul fiind de 15. Total efort: 28+15=43

Solutia mea

La fiecare pas i citim di , adaugam k la soli, dupa care cat timp t >= di si i < = n scadem din t di si citim urmatorul dx.Ne aflam la momentul cand nu mai putem alerga cu consum de energie 1 si va trebui sa adaugam fiecare pas ca suma ultimilor 2 pasi.Aici nu vom intampina probleme fiind o abordare clasica liniara.

Descarca solutia pentru problema efort,Campion 2009.

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!