1121 - p2048

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.

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python2" line="1"> f = open("p2048.in", "r") g = open("p2048.out", "w")

v = [0] * 10001 n, m, i, j, k, st, dr, p, X, Y, Z, z, s = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 d =

def main(): n, m = map(int, f.readline().split()) values = list(map(int, f.readline().split())) for i in range(n):

   v[i+1] = values[i]
   if v[i+1] == 2048:
       s = 1

st = 1 dr = n

for i in range(m):

   line = f.readline()
   d = line[0]
   z = 0

   if d == 'D':
       for j in range(dr, st, -1):
           if v[j] == v[j-1]:
               v[j] *= 2
               if v[j] == 2048:
                   s = 1
               for k in range(j-1, st, -1):
                   v[k] = v[k-1]
               st += 1
               z += 1
   else:
       for j in range(st, dr):
           if v[j] == v[j+1]:
               v[j] *= 2
               if v[j] == 2048:
                   s = 1
               for k in range(j+1, dr):
                   v[k] = v[k+1]
               dr -= 1
               z += 1

   X = i+1
   if z == 0:
       X = i
       i = m
   Z = max(Z, z)
   if s:
       i = m

Y = v[st] for i in range(st+1, dr+1):

   Y = max(Y, v[i])

g.write(str(X) + '\n' + str(Y) + '\n' + str(Z) + '\n') f.close() g.close()

if __name__ == '__main__':

  main()

</syntaxhighlight>