Fișierul intrare/ieșire	2048.in, 2048.out	Sursă	ONI 2014 clasa a 5-a
Autor	Cristina Sichim	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.5 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

2048 (clasa a 5-a)

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ă:

a) numărul X de mutări efectuate până la încheierea jocului
b) numărul maxim Y inscris pe una dintre piese la încheierea jocului
c) 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

În 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

• 2 ≤ N, M ≤ 10000
• caracterul D indică o mutare la dreapta, iar caracterul S indică o mutare la stânga
• pentru rezolvarea cerinței a) se acordă 40% din punctaj, pentru cerința b) 40% din punctaj și pentru cerința c) 20% din punctaj.

Exemplu