Fişierul intrare/ieşire:2048.in, 2048.outSursăONI 2014 clasa a 5-a
AutorCristina SichimAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

2048.in2048.outExplicaţii
7 10
16 4 4 2 2 4 8
D D S D S D S S D D
4
32
2
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
inscrisă pe una dintre piese fiind 32. Numărul maxim de fuzionări, două, a fost
obţinut la prima mutare.
Trebuie sa te autentifici pentru a trimite solutii. Click aici