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

arhin.txt

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

arhout.txt

Datele introduse corespund restrictiilor impuse.

5

aaabbbbaxyccbccd

Exemplul 2

arhin.txt

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

arhout.txt

Datele de intrare corespund restrictiilor impuse.

Exemplul 3

intrare

cbdcab

iesire

Datele de intrare nu corespund rstrictiilor impuse.

Rezolvare

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

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>