Editing 3444 - Arh

== Enunt ==

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

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

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

Un șir se consideră dezarhivat dacă este format numai din litere mici ale alfabetului englez.

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

= Date de intrare =
Fișierul de intrare <code>arhIN.txt</code> conține șirul de caractere arhivat <code>S</code>.

= Date de ieșire =
Fișierul de ieșire <code>arhOUT.txt</code> va conține obligatoriu două linii. Pe prima linie numărul de transformări cerut, iar pe linia a doua șirul de caractere cerut, <code>T</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 <</code> lungimea șirului arhivat <code>S ≤ 10000</code>; <code>0 <</code> lungimea șirului dezarhivat <code>T ≤ 100000</code>;
* <code>1 < n ≤ 1000</code>;
* O secvență a unui șir este o succesiune de caractere aflate pe poziții consecutive în şir;
* În șirul <code>S</code> 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 <code>*</code> 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 <code>S</code> poate fi dezarhivat numai cu transformări de tipul <code>1</code>;
* Pentru alte 30 de puncte șirul arhivat <code>S</code> poate fi dezarhivat numai cu transformări de tipurile <code>2</code> și <code>3</code>.
* În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

= Exemplul 1 =
<code>arhIN.txt</code>
 2(a)[*a2(b)]xy[2(c)b*]d
<code>arhOUT.txt</code>
 5
 aaabbbbaxyccbccd

=== Explicație ===
<code>2(a)</code> => <code>aa</code>

<code>2(b)</code> => <code>bb</code>

<code>[*a2(b)]</code> => <code>[*abb]</code> => <code>abbbba</code>

<code>2(c)</code> => <code>cc</code>

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

= Exemplul 2 =
<code>arhIN.txt</code>
 2(ab[cd*])a3(xyz)
<code>arhOUT.txt</code>
 3
 abcdcabcdcaxyzxyzxyz

=== Explicație ===
<code>3(xyz)</code> => <code>xyzxyzxyz</code>

<code>[cd*]</code> => <code>cdc</code>

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

== Exemplul 3 ==
<code>arhIN.txt</code>
 1001(a)[*a2(b)]xy[2(c)b*]d
<code>arhOUT.txt</code>
 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>