Editing 3444 - Arh

== Enunt ==

Dexter și-a definit propriul algoritm de arhivare a șirului favorit T, șir format numai din litere mici ale alfabetului englez. Șirul arhivat, notat cu S, poate fi format din cifre, litere mici ale alfabetului englez, parantezele drepte '[' și ']' și parantezele rotunde '(' și ')', precum și caractere '*'.

Fixi, curios din fire, descoperă algoritmul și încearcă să dezarhiveze șirul S, prin efectuarea unor transformări repetate. O transformare poate fi de unul dintre cele 3 tipuri de mai jos, unde s-a notat cu C o secvență din S formată numai din litere.

O secvență a lui S de forma n(C), unde n este numărul natural poziționat imediat înaintea parantezei rotunde, se transformă într-o secvență D obținută prin scrierea concatenată, de n ori, a șirului C. Exemplu: pentru secvența 10(ab) avem n=10 și se obține secvența D=abababababababababab.
O secvență a lui S de forma [*C] se transformă într-o secvență palindromică de lungime pară, obținută prin concatenarea secvenței C cu oglinditul lui C. Exemplu: din secvența [*abc] se obține secvența palindromică de lungime pară abccba
O secvență a lui S de forma [C*] se transformă într-o secvență palindromică de lungime impară, obținută prin concatenarea secvenței C cu oglinditul lui C din care s-a eliminat primul caracter. Exemplu: din secvența [abc*] se obține secvența palindromică de lungime impară abcba.
Un șir se consideră dezarhivat dacă este format numai din litere mici ale alfabetului englez.

== Cerinta ==

Fiind dat șirul arhivat S să se determine numărul de transformări, de cele 3 tipuri de mai sus, realizate de Fixi în cadrul algoritmului de dezarhivare, precum și forma finală dezarhivată T a șirului S.

== Date de intrare ==

Fișierul de intrare arh.in conține șirul de caractere arhivat S.

== Date de iesire ==

Fișierul de ieșire arh.out va conține obligatoriu două linii. Pe prima linie numărul de transformări cerut, iar pe linia a doua șirul de caractere cerut, T.

== Restrictii si precizari ==

*0 < lungimea șirului arhivat S ≤ 10000; 0 < lungimea șirului dezarhivat T ≤ 100000;
*1 < n ≤ 1000;
*O secvență a unui șir este o succesiune de caractere aflate pe poziții consecutive în şir;
*În șirul S o cifră poate apărea numai imediat înaintea unei paranteze rotunde deschise sau imediat înaintea unei alte cifre; fiecare paranteză rotundă deschisă are imediat înaintea sa cel puțin o cifră; toate parantezele, drepte sau rotunde, se închid corect. Caracterul * poate apărea numai imediat după o paranteză dreaptă deschisă sau imediat înaintea unei paranteze drepte închise;
*O secvenţă a unui șir este palindromică dacă primul element al secvenţei este egal cu ultimul, al doilea cu penultimul etc; oglinditul unei secvențe se obține prin scriere în ordine inversă a caracterelor sale;
*Se acordă 20% din punctajul fiecărui test pentru scrierea corectă a numărului cerut și 80% din punctajul fiecărui test pentru scrierea corectă a șirului cerut;
*Pentru 30 de puncte șirul arhivat S poate fi dezarhivat numai cu transformări de tipul 1;
*Pentru alte 30 de puncte șirul arhivat S poate fi dezarhivat numai cu transformări de tipurile 2 și 3.
*În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

== Exemplul 1 ==

; intrare 

:2(a)[*a2(b)]xy[2(c)b*]d

; iesire

: Datele introduse corespund restrictiilor impuse.

:5
:aaabbbbaxyccbccd

== Exemplul 2 ==

; intrare

:2(ab[cd*])a3(xyz)

; iesire

:Datele introduse corespund restrictiilor impuse.

== Exemplul 3 ==

; intrare 

:cbdcab

; iesire

: Datele de intrare nu corespund rstrictiilor impuse.

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">

#3444 - Arh

def dezarhiveaza(S):
    numar_transformari = 0

    while '(' in S or '[' in S:
        index_paranteza_rotunda = S.find('(')
        index_paranteza_patrata = S.find('[')

        if index_paranteza_rotunda != -1 and (index_paranteza_patrata == -1 or index_paranteza_rotunda < index_paranteza_patrata):
            # Aplică transformarea pentru secvența de forma n(C)
            paranteza_rotunda_inchisa = S.find(')', index_paranteza_rotunda)
            n = int(S[index_paranteza_rotunda + 1:paranteza_rotunda_inchisa])
            C = S[paranteza_rotunda_inchisa + 1: S.find('(', paranteza_rotunda_inchisa + 1)]
            D = n * C
            S = S[:index_paranteza_rotunda] + D + S[S.find(')', paranteza_rotunda_inchisa) + 1:]
            numar_transformari += 1

        elif index_paranteza_patrata != -1 and (index_paranteza_rotunda == -1 or index_paranteza_patrata < index_paranteza_rotunda):
            # Aplică transformarea pentru secvența de forma [*C]
            paranteza_patrata_inchisa = S.find(']', index_paranteza_patrata)
            C = S[index_paranteza_patrata + 2: paranteza_patrata_inchisa]
            D = C + C[::-1]
            S = S[:index_paranteza_patrata] + D + S[S.find(']', paranteza_patrata_inchisa) + 1:]
            numar_transformari += 1

        else:
            # Aplică transformarea pentru secvența de forma [C*]
            paranteza_patrata_inchisa = S.find(']', index_paranteza_rotunda)
            C = S[index_paranteza_rotunda + 1: paranteza_patrata_inchisa - 1]
            D = C + C[::-1][1:]
            S = S[:index_paranteza_rotunda] + D + S[S.find(']', paranteza_patrata_inchisa) + 1:]
            numar_transformari += 1

    return numar_transformari, S

</syntaxhighlight>