| Fişierul intrare/ieşire: | arh.in, arh.out | Sursă | OJI 2020, clasa a 10-a |
| Autor | Eugen Nodea | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arh
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ţe
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 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.
Exemplu
| 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© => cc [2©b*] => [ccb*] => ccbcc |
| 2(ab[cd*])a3(xyz) | 3 abcdcabcdcaxyzxyzxyz | 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. |
