Fişierul intrare/ieşire:	purice.in, purice.out	Sursă	Lot 2003
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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:

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

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.

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

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

Exemplu

Cum se trimit solutii?