Aurelia Raluca at 23:05, 22 March 2024

2024-03-22T23:05:05Z

Aurelia Raluca: /* Exemplul 3 */

2024-01-08T21:38:54Z

Exemplul 3

← Older revision		Revision as of 21:38, 8 January 2024
Line 60:		Line 60:
	== Exemplul 3 ==		== Exemplul 3 ==

	; ~~intrare~~		; arhin.txt

	:~~cbdcab~~		:hjdksk

	; ~~iesire~~		; arhout.txt

	: Datele de intrare nu corespund rstrictiilor impuse.		: Datele de intrare nu corespund rstrictiilor impuse.

Aurelia Raluca: /* Exemplul 2 */

2024-01-08T21:38:12Z

Exemplul 2

← Older revision		Revision as of 21:38, 8 January 2024
Line 56:		Line 56:
	; arhout.txt		; arhout.txt

	:Datele de intrare nu corespund restrictiilor impuse.		:Datele de intrare corespund restrictiilor impuse.

	== Exemplul 3 ==		== Exemplul 3 ==

Aurelia Raluca: /* Exemplul 2 */

2024-01-08T21:37:46Z

Exemplul 2

← Older revision		Revision as of 21:37, 8 January 2024
Line 50:		Line 50:
	== Exemplul 2 ==		== Exemplul 2 ==

	; ~~intrare~~		; arhin.txt

	:2(ab[cd*])a3(xyz)		:2(ab[cd*])a3(xyz)

	; ~~iesire~~		; arhout.txt

	:Datele ~~introduse~~ corespund restrictiilor impuse.		:Datele de intrare nu corespund restrictiilor impuse.

	== Exemplul 3 ==		== Exemplul 3 ==

Aurelia Raluca: /* Exemplul 1 */

2024-01-08T21:36:57Z

Exemplul 1

← Older revision		Revision as of 21:36, 8 January 2024
Line 36:		Line 36:
	== Exemplul 1 ==		== Exemplul 1 ==

	; ~~intrare~~		; arhin.txt

	:2(a)[a2(b)]xy[2(c)b]d		:2(a)[a2(b)]xy[2(c)b]d

	; ~~iesire~~		; arhout.txt

	: Datele introduse corespund restrictiilor impuse.		: Datele introduse corespund restrictiilor impuse.

	:5		:5

	:aaabbbbaxyccbccd		:aaabbbbaxyccbccd

Aurelia Raluca: Pagină nouă: == 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 poat...

2023-12-17T11:40:37Z

Pagină nouă: == 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 poat...

New page

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

== Cerinta ==

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 iesire ==

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.

== Restrictii si precizari ==

*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 ==

; intrare

:2(a)[*a2(b)]xy[2(c)b*]d

; iesire

: Datele introduse corespund restrictiilor impuse.

:5
:aaabbbbaxyccbccd

== Exemplul 2 ==

; intrare

:2(ab[cd*])a3(xyz)

; iesire

:Datele introduse corespund restrictiilor impuse.

== Exemplul 3 ==

; intrare

:cbdcab

; iesire

: Datele de intrare nu corespund rstrictiilor impuse.

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">

#3444 - Arh

def dezarhiveaza(S):
numar_transformari = 0

while '(' in S or '[' in S:
index_paranteza_rotunda = S.find('(')
index_paranteza_patrata = S.find('[')

if index_paranteza_rotunda != -1 and (index_paranteza_patrata == -1 or index_paranteza_rotunda < index_paranteza_patrata):
# Aplică transformarea pentru secvența de forma n(C)
paranteza_rotunda_inchisa = S.find(')', index_paranteza_rotunda)
n = int(S[index_paranteza_rotunda + 1:paranteza_rotunda_inchisa])
C = S[paranteza_rotunda_inchisa + 1: S.find('(', paranteza_rotunda_inchisa + 1)]
D = n * C
S = S[:index_paranteza_rotunda] + D + S[S.find(')', paranteza_rotunda_inchisa) + 1:]
numar_transformari += 1

elif index_paranteza_patrata != -1 and (index_paranteza_rotunda == -1 or index_paranteza_patrata < index_paranteza_rotunda):
# Aplică transformarea pentru secvența de forma [*C]
paranteza_patrata_inchisa = S.find(']', index_paranteza_patrata)
C = S[index_paranteza_patrata + 2: paranteza_patrata_inchisa]
D = C + C[::-1]
S = S[:index_paranteza_patrata] + D + S[S.find(']', paranteza_patrata_inchisa) + 1:]
numar_transformari += 1

else:
# Aplică transformarea pentru secvența de forma [C*]
paranteza_patrata_inchisa = S.find(']', index_paranteza_rotunda)
C = S[index_paranteza_rotunda + 1: paranteza_patrata_inchisa - 1]
D = C + C[::-1][1:]
S = S[:index_paranteza_rotunda] + D + S[S.find(']', paranteza_patrata_inchisa) + 1:]
numar_transformari += 1

return numar_transformari, S

</syntaxhighlight>

3444 - Arh - Revision history

Aurelia Raluca at 23:05, 22 March 2024

Aurelia Raluca: /* Exemplul 3 */

Aurelia Raluca: /* Exemplul 2 */

Aurelia Raluca: /* Exemplul 2 */

Aurelia Raluca: /* Exemplul 1 */