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

Un purice se afla pe o tabla liniara impartita in $N$ pozitii numerotate de la $1$ la $N$, oricare doua pozitii alaturate avand numere de ordine consecutive. O parte dintre aceste pozitii sunt libere, iar in fiecare dintre celelalte pozitii se afla cate un cubulet de zahar. Initial, puricele se afla pe pozitia 1 (cea mai din stanga) si doreste sa ajunga pe pozitia $N$ (cea mai din dreapta). Pentru a-si atinge scopul, puricele poate executa urmatoarele miscari:

Un purice se afla pe o tabla liniara impartita in $N$ pozitii numerotate de la $1$ la $N$, oricare doua pozitii alaturate avand numere de ordine consecutive. O parte dintre aceste pozitii sunt libere, iar in fiecare dintre celelalte pozitii se afla cate un cubulet de zahar. Initial, puricele se afla pe pozitia $1$ (cea mai din stanga) si doreste sa ajunga pe pozitia $N$ (cea mai din dreapta). Pentru a-si atinge scopul, puricele poate executa urmatoarele miscari:

* *deplasare la dreapta*: Presupunand ca puricele se afla pe pozitia $x$, atunci el se poate deplasa pe pozitia $x+1$, daca aceasta este libera, consumand o cantitate de energie $W$.
* *deplasare la stanga*: Presupunand ca puricele se afla pe pozitia $x$, atunci el se poate deplasa pe pozitia $x-1$, daca aceasta este libera, consumand o cantitate de energie $W$.

h2. Date de intrare

Pe prima linie a fisierului de intrare $purice.in$ se afla 4 numere intregi $N W J P$ (avand semnificatiile descrise mai sus). Pe cea de a doua linie a fisierului se afla o secventa de $N$ caractere din mult£imea ${0,1}$, ce descriu cele $N$ pozitii: $0$ inseamna ca pozitia respectiva este libera, iar $1$ ca este ocupata de un cub de zahar.

Pe prima linie a fisierului de intrare $purice.in$ se afla 4 numere intregi $N W J P$ (avand semnificatiile descrise mai sus). Pe cea de a doua linie a fisierului se afla o secventa de $N$ caractere din mult£imea ${0,1}$, ce descriu cele $N$ pozitii: $0$ inseamna ca pozitia respectiva este libera, iar $1$ ca este ocupata de un cub de zahar.

h2. Date de iesire

* Initial, pozitiile $1$ si $N$ sunt libere.
* In cazul testelor folosite, va exista cel putin o succesiune valida de miscari ale puricelui care sa il aduca de pe pozitia $1$ pe pozitia $N$.
* La evaluare se vor folosi $20$ de teste. Punctajul pentru fiecare test se acorda in felul urmator:

** Daca succesiunea de miscari descrisa in fisierul de iesire nu este valida sau, in urma executarii ei, puri­cele nu ajunge pe pozitia $N$ sau cantitatea de energie consumata de purice in urma executarii tuturor miscarilor nu este egala cu numarul scris pe prima linie a fisierului de iesire, veti primi $0$ puncte

** Daca succesiunea de miscari descrisa in fisierul de iesire nu este valida sau, in urma executarii ei, puri­cele nu ajunge pe pozitia $N$ sau cantitatea de energie consumata de purice in urma executarii tuturor miscarilor nu este egala cu numarul scris pe prima linie a fisierului de iesire, veti primi $0$ puncte

** Altfel, sa presupunem ca $M$ este cantitatea minima de energie consumata de purice pentru a ajunge in pozitia finala si $A$ este cantitatea de energie determinata de programul dumneavoastra
*** Daca $A = M$, veti primi $5$ puncte
*** Daca $M < A ≤ 1.15*M$, veti primi $4$ puncte