Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Nu te descurci?

Urmărește indicațiile pentru a înțelege cum se rezolvă problema.

Problemă verificată: Problemă de concurs certificată de InfoAs: Soluțiile tale trimise la această problemă sunt evaluate în exact același mediu ca și la concurs.

OJI 2020, clasa a X-a · Clasa a X-aStructuri de date liniareProbleme cu stivă

Problema Arh

Grea (8 )

Memorie: 64 MB / 16 MB

Timp: 0.5 secunde

I/O: Fișiere

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.

  1. 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;
  2. 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;
  3. 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ță

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 ≤ 10.000
  • 0 < lungimea șirului dezarhivat T ≤ 100.000
  • 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

Exemple

2(a)[*a2(b)]xy[2(c)b*]d
5
aaabbbbaxyccbccd
2(ab[cd*])a3(xyz)
3
abcdcabcdcaxyzxyzxyz
abcd
0
abcd

Explicația exemplelor

Pentru primul exemplu:

  • 2(a) --> aa
  • 2(b) --> bb
  • [*a2(b)] --> [*abb] --> abbbba
  • 2(c) --> cc
  • [2(c)b*] --> [ccb*] --> ccbcc

Problemă adăugată pe InfoAs de  Poza de profil a utilizatorului @concursuriOlimpiade și concursuri

Se încarcă…

Se încarcă…

Se încarcă…

Se încarcă…

Rezolvarea ta


							

							

						

						

							
														
							
														
						

					

										

						

							
Nu ești logat!

							
Loghează-te pentru a putea testa rezolvarea ta la această problemă.

						

					

									

			

		

				

			
			
Posibile greșeli

			
Am detectat următoarele posibile greșeli în codul tău. De regulă, aceste greșeli trec de compilare, însă au un comportament impredictibil în evaluarea codului (ducând astfel la punctaje mai mici).


			
    
		
    
		
    
			
			
    Setări editor
    

			
    Stil editor (CTRL + Shift + E)
    
			
    Atenție: Pe ecranele mici, schimbarea stilului editorului nu are niciun efect.
    
			
			
    
			
			

			
    Afișează confetti
    
			
			
    
		
    
			
			
    De ce nu iau 100 de puncte?
    

			
    Răspuns greșit
    
			
    Dacă răspunsul tău la un test este 100% corect, dar totuși este marcat ca fiind greșit, poate fi din următoarele cauze:

    
			
    Afișezi și alte lucruri. De exemplu, dacă vrei să citești un număr de la tastatură, corect este cin >> n;, iar greșit este cout << "n="; cin >> n; – mai precis, nu afișa niciun mesaj când faci citirea, deoarece este considerat parte din răspuns. Asemănător și pentru afișare (doar răspunsul trebuie afișat, exact cum este specificat în cerință, nimic altceva).

    
			
    Nu dai o valoare de început unei variabile locale. În CodeBlocks, când rulezi un program, există posibilitatea ca variabilele declarate în int main() fără o valoare de început, de pildă int nr;, să le fie atribuite valoarea 0. Acest lucru nu este deloc garantat în majoritatea mediilor de programare, de regulă aceste variabile având valori aleatorii. Astfel, este indicat să dai o valoare implicită tuturor variabilelor pe care le declari în int main(), în special cele de contorizare: int nr = 0;.

    
			
    Nu afișezi unde trebuie. La această problemă, citirea și afișarea se realizează din fișiere. Poate citești și afișezi prin consolă

    
			
    Probleme cu memoria (în special la vectori sau matrici). De regulă, problemele de memorie dau fatal signal 11 (vezi mai jos pentru detalii). Însă, există posibilitatea să existe anumite erori mai subtile, care totuși dau răspuns greșit în ciuda faptului că este o problemă de memorie. Un exemplu ar fi, în anumite condiții, declararea unui vector int a[100]; și efectuarea diferitelor operații cu poziția a[100] a sa (vectorul are doar poziții de la 0 la 99, dar accesăm poziția 100).

    

			
    Caught fatal signal 11
    
			
    Probleme cu memoria (în special la vectori sau matrici). Această eroare apare când încerci să accesezi zone de memorie interzise, sau în general făcând lucruri dubioase cu memoria. Iată câteva exemple tipice:
    
			
    
			
    Depășești limita de memorie. Fiecare problemă are o limită de memorie, care, de regulă, este destul de generoasă. Există șansa să depășești totuși limita de memorie, fapt care duce la această eroare. Un exemplu ar fi ca, la o problemă cu limita impusă de 2 MB, să fie declarat un vector int a[1000000]; (cu un milion de elemente), care are aproximativ 3.81 MB.

    

			
    Caught fatal signal 4 / caught fatal signal 8
    
			
    Împarți un număr la zero. Această eroare apare doar dacă, undeva în cod, împarți la 0. Poate fi ori evident (ai scris n /= 0; în loc de n /= 10;, de exemplu), ori poate fi mai subtil (ai o variabilă x care, cumva, reușește să ia valoarea 0, și efectuezi n / x).

    
			
    Extragi rădăcina pătrată dintr-un număr negativ. Această eroare apare doar dacă, undeva în cod, aplici sqrt(n), unde n este un număr negativ. Poate fi ori evident (ai scris sqrt(-4); în loc de sqrt(4);, de exemplu), ori poate fi mai subtil (ai o variabilă x care, cumva, reușește să ia o valoare negativă, și efectuezi sqrt(x)).

    

			
    Eroare de compilare (E.C.)
    
			
    Codul tău conține o eroare de scriere. Nu am apucat să îți testăm codul, deoarece acesta conține o greșeală – sub mesajul Eroare de compilare se află o explicație unde poți să vezi exact pe ce linii ai erori. Cel mai probabil ai uitat să pui un ; (punct și virgulă) pe undeva, sau ai uitat să incluzi o bibliotecă.

    

			
    Altă eroare
    
			
    Dacă ați întâmpinat altă eroare, ne puteți informa pe formularul de feedback.
    
		
    
		
    
			
    Înainte să continui…
    

			
    Urmează să rezolvi prima ta problemă pe InfoAs! Asigură-te că nu afișezi niciun alt mesaj decât ceea ce îți cere problema, altfel, vei obține răspuns greșit. De pildă:
    
			
    
				
    Iconita warning Nu trebuie afișat mesajul "Suma este "! Se vor obține 0 puncte, pentru răspuns greșit.
    
				cout << "Suma este " << s;
			
    
			
    
				
    Iconita bine Afișarea este corectă.
    
				cout << s;