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 forman(C)
, unden
este numărul natural poziționat imediat înaintea parantezei rotunde, se transformă într-o secvențăD
obținută prin scrierea concatenată, den
ori, a șiruluiC
. Exemplu: pentru secvența10(ab)
avemn=10
și se obține secvențaD=abababababababababab
. - O secvență a lui
S
de forma[*C]
se transformă într-o secvență palindromică de lungime pară, obținută prin concatenarea secvențeiC
cu oglinditul luiC
. 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țeiC
cu oglinditul luiC
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 arhivatS ≤ 10000
;0 <
lungimea șirului dezarhivatT ≤ 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 tipul1
; - Pentru alte 30 de puncte șirul arhivat
S
poate fi dezarhivat numai cu transformări de tipurile2
și3
. - Î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
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()