Pls Traian intră în concurs | 2048

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 2MB Input: 2048.in Output: 2048.out

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

  • se pornește de la un șir de NN piese pe care sunt înscrise numere din mulțimea {22, 44, 88, 1616, 3232, 6464, 128128, 256256, 512512, 10241024, 20482048};
  • piesele sunt așezate în locații numerotate consecutiv cu numerele 11, 22, ..., NN;
  • 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 MM;

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 ii și are înscrisă valoarea kk, iar pe poziția i+1i+1 se află o piesă cu aceeași valoare kk, atunci aceste piese vor "fuziona", pe poziția i+1i+1 se va obține o piesă cu valoarea 2k2k, iar pe poziția ii 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 nn;

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 ii și are înscrisă valoarea kk, iar pe poziția i1i-1 se află o piesă cu aceeași valoare kk, atunci aceste piese vor "fuziona", pe poziția i1i-1 se va obține o piesă cu valoarea 2k2k, iar pe poziția ii 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 11;

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 20482048;
  • valorile înscrise nu se mai pot modifica prin mutarea pieselor;
  • s-au efectuat toate cele MM mutări.

Cerinţe

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

  1. numărul XX de mutări efectuate până la încheierea jocului;
  2. numărul maxim YY inscris pe una dintre piese la încheierea jocului;
  3. numărul maxim ZZ 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 NN și MM. A doua linie a fişierului conţine cele NN numere inscrise, în ordine, pe piese, separate prin câte un spaţiu. A treia linie a fișierului conține cele MM caractere, separate prin câte un spaţiu, ce reprezintă cele MM direcții de mutare.

Date de ieşire

Fişierul de ieşire 2048.out va conţine pe prima linie numărul XX, pe a doua linie numărul YY și pe a treia linie numărul ZZ.

Restricţii şi precizări

  • 2N,M10 0002 \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 11 se acordă 40%40\% din punctaj
  • pentru rezolvarea cerinţei 22 se acordă 40%40\% din punctaj
  • pentru rezolvarea cerinţei 33 se acordă 20%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 11.
Au fost efectuate 44 mutări până la încheierea jocului, cea mai mare valoare înscrisă pe una dintre piese fiind 3232. Numărul maxim de fuzionări, două, a fost obținut la prima mutare.

Log in or sign up to be able to send submissions!