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.

1. 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.
2. 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
3. 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.

Cerința

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 arhIN.txt conține șirul de caractere arhivat S.

Date de ieșire

Fișierul de ieșire arhOUT.txt 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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 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

5
aaabbbbaxyccbccd

Explicație

2(a) => aa

2(b) => bb

[*a2(b)] => [*abb] => abbbba

2(c) => cc

[2(c)b*] => [ccb*] => ccbcc

Exemplul 2

arhIN.txt

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

arhOUT.txt

3
abcdcabcdcaxyzxyzxyz

Explicație

3(xyz) => xyzxyzxyz

[cd*] => cdc

2(ab[cd*]) => 2(abcdc) => abcdcabcdc

Exemplul 3

arhIN.txt

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

arhOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> fin = None fout = None s = "" transf = 0 p = 0

def repeatOp():

   global p, transf
   transf += 1
   ori = 0
   while p < len(s) and s[p].isdigit():
       ori = ori * 10 + int(s[p])
       p += 1

   p += 1  # sar peste '('
   ans, deRepetat = "", ""
   
   while s[p] != ')':
       deRepetat += termen()
   p += 1  # sar peste ')'
   
   while ori > 0:
       ans += deRepetat
       ori -= 1

   return ans

def palParOp():

   global p, transf
   transf += 1
   p += 2  # sar peste '[*'
   ans = ""
   
   while s[p] != ']':
       ans += termen()
       
   for i in range(len(ans) - 1, -1, -1):
       ans += ans[i]
   p += 1  # sar peste ']'
   
   return ans

def palImpOp():

   global p, transf
   transf += 1
   p += 1  # sar peste '['
   ans = ""

   while s[p] != '*':
       ans += termen()
   
   for i in range(len(ans) - 2, -1, -1):
       ans += ans[i]
   p += 2  # sar peste '*]'
   
   return ans

def termen():

   global p
   ans = ""
   if s[p].isdigit():
       ans = repeatOp()
   elif s[p] == '[' and s[p + 1] == '*':
       ans = palParOp()
   elif s[p] == '[':
       ans = palImpOp()
   elif s[p].isalpha():
       ans = s[p]
       p += 1

   return ans

def eval():

   ans = ""
   while p < len(s):
       ans += termen()
   
   return ans

def check_constraints(s, n):

   if not (0 < len(s) <= 10000 and 1 < n <= 1000):
       return False
   return True

def main():

   global s
   with open("arhIN.txt", "r") as fin:
       s = fin.readline().strip()

   # Extragem n din șirul arhivat
   if '(' in s:
       n = int(s.split('(')[0])
   else:
       with open("arhOUT.txt", "w") as fout:
           fout.write("Datele nu corespund restrictiilor impuse")
       return

   if not check_constraints(s, n):
       with open("arhOUT.txt", "w") as fout:
           fout.write("Datele nu corespund restrictiilor impuse")
       return

   ans = eval()

   with open("arhOUT.txt", "w") as fout:
       fout.write(f"{transf}\n{ans}")

if __name__ == "__main__":

   main()

</syntaxhighlight>