== include(page="template/taskheader" task_id="arh") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

* 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$.

Fişierul de intrare $arh.in$ ...

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

h2. Date de ieşire

h2. Cerinţe

În fişierul de ieşire $arh.out$ ...

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$.

h2. Restricţii

h2. Date de intrare

* $... ≤ ... ≤ ...$

Fişierul de intrare $arh.in$ conţine şirul de caractere arhivat $S$.

h2. Exemplu

h2. Date de ieşire
 
Fişierul de ieşire $arh.out$ conţine obligatoriu două linii. Pe prima linie numărul de transformări cerut, iar pe linia a doua şirul de caractere cerut, $T$.

table(example). |_. arh.in |_. arh.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h2. 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$.

h3. Explicaţie

h2. Exemplu

...

table(example). |_. arh.in |_. arh.out |_. Explicaţie |
| 2(a)[*a2(b)]xy[2(c)b*]d
| 5
aaabbbbaxyccbccd
| 2(a) => aa
2(b) => bb
[*a2(b)] => [*abb] => abbbba
2(c) => cc
[2(c)b*] => [ccb*] => ccbcc
|
| 2(ab[cd*])a3(xyz)
| 3
abcdcabcdcxyazxyzxyz
| 3(xyz) => xyzxyzxyz
[cd*] => cdc
2(ab[cd*]) => 2(abcdc) => abcdcabcdc
|
| abcd
| 0
abcd
| Nu este nevoie de nicio transformare, iar şirul dezarhivat este identic cu cel arhivat.
|

== include(page="template/taskfooter" task_id="arh") ==