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

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()