# PBinfo #1121 – p2048 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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 2•k, 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 2•k, 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 înscris 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 p2048.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 înscrise, î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 p2048.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 ≤ 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:
p2048.in

7 10 
16 4 4 2 2 4 8
D D S D S D S S D D
p2048.out

4
32
2
Explicație
Succesiunea de mutări este reprezentată în figura de mai sus. 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.

## Cod sursă C++

```cpp
//Cristina Sichim, C.N. Ferdinand I Bacau
#include <fstream>
using namespace std;
ifstream f("p2048.in");
ofstream g("p2048.out");
int v[10001],n,m,i,j,k,st,dr,p,X,Y,Z,z,s;
char d;
int main()
{ f>>n>>m;
  for(i=1;i<=n;++i){f>>v[i]; if(v[i]==2048) s=1;}
  st=1;dr=n;
  for(i=1;i<=m && !s;i++)
  { f>>d;
    z=0;
    if(d=='D')
      {for(j=dr;j>st;j--)
         if(v[j]==v[j-1]) {v[j]*=2;
                           if(v[j]==2048) s=1;
                           for(k=j-1;k>st;k--)v[k]=v[k-1];
                           st++;
                           z++;
                          }
      }
    else
     { for(j=st;j<dr;j++)
          if(v[j]==v[j+1]){ v[j]*=2;
                            if(v[j]==2048) s=1;
                            for(k=j+1;k<dr;k++)v[k]=v[k+1];
                            dr--;
                            z++;
                          }
     }
     X=i;
     if(z==0) X=i-1,i=m;
     Z=max(Z,z);
     if(s)i=m;
  }
Y=v[st];
for(i=st+1;i<=dr;i++)  Y=max(Y,v[i]);
g<<X<<'\n'<<Y<<'\n'<<Z<<'\n';
f.close();g.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1121)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1121/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1121/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)