Editing 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 <code>N</code> piese pe care sunt înscrise numere din mulțimea <code>{2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}</code>;
* piesele sunt așezate în locații numerotate consecutiv cu numerele  <code>1,2,…, N</code>;
* 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 <code>M</code>;
* 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 <code>i</code> și are înscrisă valoarea <code>k</code>, iar pe poziția <code>i+1</code> se află o piesă cu aceeași valoare <code>k</code>, atunci aceste piese vor “fuziona”, pe poziția <code>i+1</code> se va obține o piesă cu valoarea <code>2•k</code>, iar pe poziția <code>i</code> 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 <code>i</code> și are înscrisă valoarea <code>k</code>, iar pe poziția <code>i-1</code> se află o piesă cu aceeași valoare <code>k</code> , atunci aceste piese vor “fuziona”, pe poziția <code>i-1</code> se va obține o piesă cu valoarea <code>2•k</code>, iar pe poziția <code>i</code> 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 <code>1</code>;
* 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 <code>2048</code>;
** valorile înscrise nu se mai pot modifica prin mutarea pieselor;
** s-au efectuat toate cele <code>M</code> mutări.

= Cerinţe =
Scrieţi un program care să citească numerele naturale <code>N</code> (numărul inițial de piese) și <code>M</code> (numărul maxim de mutări),  un șir de <code>N</code> numere reprezentând, în ordine, numerele înscrise pe cele <code>N</code> piese și cel mult <code>M</code> caractere din mulțimea <code>{S, D}</code> ce reprezintă mutările fixate de către Ada și Ben, și care determină: 

a) numărul <code>X</code> de mutări efectuate până la încheierea jocului;  

b) numărul maxim <code>Y</code> înscris pe una dintre piese la încheierea jocului;  

c) numărul maxim <code>Z</code> de fuzionări efectuate la o mutare.

= Date de intrare =
Fișierul de intrare <code>p2048.in</code> conține pe prima linie, separate  prin câte un spaţiu, numerele <code>N</code> și <code>M</code>. A doua linie a fişierului conţine cele <code>N</code> numere înscrise, în ordine, pe piese, separate prin câte un spaţiu. A treia linie a fișierului conține cele <code>M</code> caractere, separate prin câte un spaţiu, ce reprezintă cele <code>M</code> direcții de mutare.

= Date de ieșire =
Fișierul de ieșire <code>p2048.out</code> va conține pe prima linie numărul <code>X</code>, pe a doua linie numărul <code>Y</code> și pe a treia linie numărul <code>Z</code>.

= Restricții și precizări =

* <code>2 ≤ N,M ≤ 10000</code>;
* caracterul <code>D</code> indică o mutare la dreapta, iar caracterul <code>S</code> 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: =
<code>p2048.in</code>
 7 10 
 16 4 4 2 2 4 8
 D D S D S D S S D D
<code>p2048.out</code>
 4
 32
 2

= Explicație =
Succesiunea de mutări este reprezentată în figura de mai sus. Au fost efectuate <code>4</code> mutări până la încheierea jocului, cea mai mare valoare înscrisă pe una dintre piese fiind <code>32</code>. 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>