Pentru a putea rula codul, te rugăm să te autentifici.

main.cpp

ID #721 · Olimpiada Județeană de Informatică 2020, clasa a X-a · Probleme cu stivă

Problema Arh

Dificilă · 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.

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ță

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

arh.in

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

arh.out

5
aaabbbbaxyccbccd

Explicație

Pentru primul exemplu:

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

arh.in

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

arh.out

3
abcdcabcdcaxyzxyzxyz

Explicație

Pentru primul exemplu:

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

arh.in

abcd

arh.out

0
abcd

Explicație

Pentru primul exemplu:

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

ID	#721	Autor	OJI 2020, clasa a X-a
Set	Olimpiada Județeană de Informatică 2020, clasa a X-a	Adăugată de	Alexis Alexis lexington
Capitol	Clasa a X-a/Structuri de date liniare/Probleme cu stivă
Licență	Problema aceasta a fost publicată sub licența CC BY-SA 4.0. Indicațiile sunt publicate sub licența CC BY-SA 4.0, iar rezolvarea sub licența CC BY-SA 4.0. Licența InfoAs Standard License nu permite copierea sau modificarea fără acordul scris al autorilor. Platforma și toate funcționalitățile ei rămân în continuare proprietatea intelectuală Aspire Education Labs SRL. © 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Indicații oficiale de rezolvare a problemei

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem:

Pentru a vizualiza indicațiile problemei, te rugăm să te autentifici.

Autentifică-te

Indicații oficiale de rezolvare a problemei

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem:

Pentru a vizualiza rezolvarea problemei, te rugăm să te autentifici.

Autentifică-te

Soluții trimise la problema Arh

Soluții trimise	7
Soluții de 100 de puncte	5
Soluții de luna aceasta La fel de multe ca luna trecută.	0 +0
Rata de succes Rata dintre numărul de persoane care au obținut 100 de puncte și numărul total de persoane care au încercat problema.	80%

Autentifică-te pentru a vedea soluțiile tale.

Autentifică-te

Toate soluțiile tale le găsești aici. Găsești toate detaliile evaluării mai târziu, precum punctaje și sfaturi primite.
Poți să editezi soluțiile tale și să le retrimiți. Reia mai târziu de unde ai rămas, pentru că poți modifica soluții și să le reevaluezi.
Profesorii pot să vadă soluțiile tale și să îți trimită sugestii. Astfel, îți este mai ușor să înveți informatica, primind sfaturi bune chiar de la școală.

Ultimele soluții trimise 7

100000	1000	100000	1000000	10
1000	100	10	10000	1000000
1000000	1000	100	100000	10000
100000	100000	10000000	1000000	1000
1000	100	10	10000	10000
10000	1000	1000000	10000	1000
100000	100	10000	100	10000000
10	100000	10	1000000	10000000
10000	100	100000	10000000	10
1000	10000000	10000000	100	10
Tabelul se actualizează în timp real. ?? / ??

Căutare probleme sau lecții	`/`
Primul rezultat	`Enter`
Rulează codul	`Ctrl + Enter`
Meniu shortcuturi	`?`
Ieși din meniul curent	`Esc`

Bacalaureat și admiteri

Olimpiade și concursuri

Rezolvă probleme

Materia de olimpiadă

Problema Arh

Cerință

Date de intrare

Date de ieșire

Restricții și precizări

Exemple

arh.in

arh.out

Explicație

arh.in

arh.out

Explicație

arh.in

arh.out

Explicație

Indicații oficiale de rezolvare a problemei

Subtitle

Indicații oficiale de rezolvare a problemei

Subtitle

Soluții trimise la problema Arh

Statistici

Autentifică-te pentru a vedea soluțiile tale.

Ultimele soluții trimise 7

Comentarii 0

Autentifică-te pentru a putea comenta.

Prelucrare text

Testare cod

InfoAs AI

Bacalaureat și admiteri

Olimpiade și concursuri

Rezolvă probleme

Materia de olimpiadă

Problema Arh

Cerință

Date de intrare

Date de ieșire

Restricții și precizări

Exemple

arh.in

arh.out

Explicație

arh.in

arh.out

Explicație

arh.in

arh.out

Explicație

Indicații oficiale de rezolvare a problemei

Subtitle

Indicații oficiale de rezolvare a problemei

Subtitle

Soluții trimise la problema Arh

Statistici

Autentifică-te pentru a vedea soluțiile tale.

Ultimele soluții trimise 7

Comentarii 0

Autentifică-te pentru a putea comenta.

Prelucrare text

Testare cod

InfoAs AI

Setări

Dispunere

Alte setări

Utilizăm Cookies

Shortcuturi