Problem 1430: 2048

Ada și Ben sunt pasionați de jocurile pe calculator și tocmai au descoperit cea mai recentă versiune a jocului $2048$ .
Regulile jocului sunt foarte simple:

se pornește de la un șir de $N$ piese pe care sunt înscrise numere din mulțimea { $2$ , $4$ , $8$ , $16$ , $32$ , $64$ , $128$ , $256$ , $512$ , $1024$ , $2048$ };
piesele sunt așezate în locații numerotate consecutiv cu numerele $1$ , $2$ , ..., $N$ ;
la fiecare pas, poate avea loc o MUTARE la STÂNGA sau o MUTARE la DREAPTA;
pentru fiecare joc este stabilit un număr maxim de mutări $M$ ;

Dacă are loc o MUTARE la DREAPTA, atunci:

piesele pot fuziona la dreapta, începând cu penultima piesă din şir: dacă o piesă se află pe o poziție $i$ și are înscrisă valoarea $k$ , iar pe poziția $i+1$ se află o piesă cu aceeași valoare $k$ , atunci aceste piese vor "fuziona", pe poziția $i+1$ se va obține o piesă cu valoarea $2k$ , iar pe poziția $i$ rămâne o locație liberă;
după efectuarea fuzionărilor, piesele se aliniază la dreapta, astfel încât ultima piesă să se afle pe poziția $n$ ;

Dacă are loc o MUTARE la STÂNGA, atunci:

piesele pot fuziona la stânga, începând cu a doua piesă din șir: dacă o piesă se află pe o poziție $i$ și are înscrisă valoarea $k$ , iar pe poziția $i-1$ se află o piesă cu aceeași valoare $k$ , atunci aceste piese vor "fuziona", pe poziția $i-1$ se va obține o piesă cu valoarea $2k$ , iar pe poziția $i$ rămâne o locație liberă;
după efectuarea fuzionărilor, piesele se aliniază la stânga, astfel încât prima piesă să se afle pe poziția $1$ ;

Jocul se încheie atunci când se ajunge în una dintre următoarele situații:

pe cel puțin una dintre piese se află înscrisă valoarea $2048$ ;
valorile înscrise nu se mai pot modifica prin mutarea pieselor;
s-au efectuat toate cele $M$ mutări.

Cerinţe

Scrieţi un program care să citească numerele naturale $N$ (numărul inițial de piese) și $M$ (numărul maxim de mutări), un șir de $N$ numere reprezentând, în ordine, numerele înscrise pe cele $N$ piese și cel mult $M$ caractere din mulțimea {S, D} ce reprezintă mutările fixate de către Ada și Ben, și care determină:

numărul $X$ de mutări efectuate până la încheierea jocului;
numărul maxim $Y$ inscris pe una dintre piese la încheierea jocului;
numărul maxim $Z$ de fuzionări efectuate la o mutare.

Date de intrare

Fişierul de intrare 2048.in conţine pe prima linie, separate prin câte un spaţiu, numerele $N$ și $M$ . A doua linie a fişierului conţine cele $N$ numere inscrise, în ordine, pe piese, separate prin câte un spaţiu. A treia linie a fișierului conține cele $M$ caractere, separate prin câte un spaţiu, ce reprezintă cele $M$ direcții de mutare.

Date de ieşire

Fişierul de ieşire 2048.out va conţine pe prima linie numărul $X$ , pe a doua linie numărul $Y$ și pe a treia linie numărul $Z$ .

Restricţii şi precizări

$2 \leq N,M \leq 10 \ 000$ ;
caracterul D indică o mutare la dreapta, iar caracterul S indică o mutare la stânga;
pentru rezolvarea cerinţei $1$ se acordă $40\%$ din punctaj
pentru rezolvarea cerinţei $2$ se acordă $40\%$ din punctaj
pentru rezolvarea cerinţei $3$ se acordă $20\%$ din punctaj

Exemplu

2048.in

7 10
16 4 4 2 2 4 8
D D S D S D S S D D

2048.out

4
32
2

Explicație

Succesiunea de mutări este reprezentată în figura $1$ .
Au fost efectuate $4$ mutări până la încheierea jocului, cea mai mare valoare înscrisă pe una dintre piese fiind $32$ . Numărul maxim de fuzionări, două, a fost obținut la prima mutare.

2048