== include(page="template/taskheader" task_id="purice") ==
Poveste si cerinta...
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$.
* *salt la dreapta*: Pentru a putea sari, puricele trebuie sa isi ia avant. Astfel, daca ultimele $K$ {$(K ≥ 1)$} miscari ale sale au fost toate deplasari la dreapta, atunci puricele poate sari intre $1$ si $K+1$ pozitii. Presupunand ca pozitia sa este $x$, dupa un salt la dreapta de $Q$ pozitii, puricele se va afla pe pozitia $x + Q$. Aceasta pozitie trebuie sa fie libera. Indiferent de numarul de pozitii peste care sare, puricele consuma o cantitate de energie $J$.
* *salt la stanga*: Daca ultimele $K$ {$(K ≥ 1)$} miscari ale puricelui au fost toate deplasari la stanga, atunci el poate sari intre $1$ si $K+1$ pozitii. Presupunand ca pozitia sa este $x$, dupa un salt la stanga de $Q$ pozitii, puricele se va afla pe pozitia $x - Q$. Aceasta pozitie trebuie sa fie libera. Indiferent de numarul de pozitii peste care sare, puricele consuma o cantitate de energie $J$.
* *impingere la dreapta*: Presupunem ca puricele se afla pe pozitia $x$. Daca pozitia $x + 1$ contine un cub de zahar, atunci puricele poate impinge acest cub o pozitie la dreapta. In urma executarii acestei operatii, toate cuburile de pe pozitiile $x + 1, x + 2, ..., x + K - 1$, unde $x + K$ este prima pozitie libera din dreapta puricelui, se vor deplasa cu o pozitie la dreapta. Daca nu exista nici o pozitie libera la dreapta puricelui, atunci operatia nu este permisa. Pentru o impingere, puricele consuma o cantitate de energie $P$. In urma operatiei de impingere la dreapta, noua pozitie a puricelui va fi $x + 1$.
* *impingere la stanga*: Presupunem ca puricele se afla pe pozitia $x$. Daca pozitia $x - 1$ contine un cub de zahar, atunci puricele poate impinge acest cub o pozitie la stanga. In urma executarii acestei operatii, toate cuburile de pe pozitiile $x - 1, x - 2, ..., x - K + 1$, unde $x - K$ este prima pozitie libera din stanga puricelui, se vor deplasa o pozitie la stanga. Daca nu exista nici o pozitie libera la stanga puricelui, atunci operatia nu este permisa. Pentru o impingere, puricele consuma o cantitate de energie $P$. In urma operatiei de impingere la stanga, noua pozitie a puricelui va fi $x - 1$.
Scrieti un program care determina cantitatea minima de energie pe care o va consuma puricele pentru a ajunge pe pozitia $N$, precum si o secventa de miscari ale acestuia.
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 multimea ${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
...
Pe prima linie a fisierului de iesire $purice.out$ veti afisa cantitatea minima de energie necesara puricelui pentru a ajunge pe pozitia $N$. Pe urmatoarele linii veti descrie miscarile efectuate de catre purice (cate o miscare pe linie). Miscarile vor fi codificate astfel:
* $"WR"$ - pentru o deplasare la dreapta
* $"WL"$ - pentru o deplasare la stanga
* $"JR" K$ - pentru un salt la dreapta; dupa sirul $JR$ urmeaza un spatiu si apoi un intreg $K$ {$(K ≥ 1)$}, reprezentand numarul de pozitii pe care le va sari puricele (in urma acestei operatii, pozitia puricelui va creste cu K unitati)
* $"JL" K$ - pentru un salt la stanga; dupa sirul $JL$ urmeaza un spatiu si apoi un intreg $K$ {$(K ≥ 1)$}, reprezentand numarul de pozitii pe care le va sari puricele (in urma acestei operatii, pozitia puricelui va scadea cu $K$ unitati)
* $"PR"$ - pentru o impingere la dreapta
* $"PL"$ - pentru o impingere la stanga
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100$
* $0 ≤ W, J, P ≤ 100 000$
* Pozitia puricelui va trebui sa fie intotdeauna in intervalul $1..N$.
* 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, puricele 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
*** Daca $1.15*M < A ≤ 1.5*M$, veti primi $3$ puncte
*** Daca $1.5*M < A ≤ 2*M$, veti primi $2$ puncte
*** Daca $A > 2*M$, veti primi $1$ punct
h2. Exemplu
table(example). |_. purice.in |_. purice.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|8 2 2 3
00110010
|20
WR
PR
PR
WL
JL 2
WR
WR
WR
JR 4
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="purice") ==
