Fișierul intrare/ieșire 2048.in, 2048.out Sursă ONI 2014 clasa a 5-a
Autor Cristina Sichim Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.5 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in 2048.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii