# PBinfo #3444 – Arh – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț 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. 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 arh.in conține șirul de caractere arhivat S. Date de ieșire 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. 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 arh.in 2(a)[*a2(b)]xy[2(c)b*]d arh.out 5 aaabbbbaxyccbccd Explicație 2(a) => aa 2(b) => bb [*a2(b)] => [*abb] => abbbba 2(c) => cc [2(c)b*] => [ccb*] => ccbcc Exemplul 2 arh.in 2(ab[cd*])a3(xyz) arh.out 3 abcdcabcdcaxyzxyzxyz Explicație 3(xyz) => xyzxyzxyz [cd*] => cdc 2(ab[cd*]) => 2(abcdc) => abcdcabcdc Exemplul 3 arh.in abcd arh.out 0 abcd Explicație Nu este nevoie de nicio transformare, iar șirul dezarhivat este identic cu cel arhivat. ## Cod sursă C++ ```cpp /// Sursa oficiala - 100p /// prof. Eugen Nodea # include using namespace std; ifstream f("arh.in"); ofstream g("arh.out"); string T, S; int i, L, nra; string eval1(); /// calculeaza parantezele () string eval2(); /// calculeaza parantezele [] string sir(); /// formeaza sir de caractere int numar(); /// formeaza numarul void eval() { while (i < T.size()) { S += sir(); int nr = numar(); if (nr) { string r1 = eval1(); for(int j=1; j<=nr; ++j) S += r1; } else if (T[i] == '[')S += eval2(); else S += sir(); } } string eval1() { string r = ""; if (T[i] == '(') i++; while (T[i] != ')') { r += sir(); if (T[i] == '[') r += eval2(); r += sir(); int nr = numar(); if (nr) { string r1 = eval1(); for(int j=1; j<=nr; ++j) r += r1; } r += sir(); } i++; return r; } string eval2() { int par = 0; string r = "", r1 = ""; if (T[i] == '[') i++; if (T[i] == '*') par = 1, i++; while (T[i] != ']') { r += sir(); if (T[i] == '[') r += eval2(); if (isdigit(T[i])) { int nr = numar(); string r1 = eval1(); for(int j=1; j<=nr; ++j) r += r1; } r += sir(); if (T[i] == '*') i++; } if (T[i] == ']') { r1 = r; if (!par) { r1.erase(r1.end()-1); } reverse(r1.begin(), r1.end()); i++; } return r + r1; } string sir() { string r = ""; while(isalpha(T[i])) r += T[i], i++; return r; } int numar() { int r = 0; while (isdigit(T[i])) { r = r * 10 + (T[i] - '0'); i++; } return r; } int main() { f >> T; L = T.size(); for(int i=0; i