|
|
| Line 1: |
Line 1: |
| = Structuri de date elementare =
| |
| Stivele şi cozile sunt mulţimi dinamice în care elementul care este eliminat din mulţime de către operaţia Şterge este prespecificat. Într-o stivă, elementul şters din mulţime este elementul cel mai recent inserat: stiva implementează principiul ultimul sosit, primul servit (last-in, first-out) sau LIFO. Similar, într-o coadă, elementul şters este întotdeauna cel care a stat în mulţime cel mai mult (primul introdus): coada implementează principiul primul sosit, primul servit (first-in, first-out) sau FIFO. Există mai multe modalităţi eficiente de a implementa stivele şi cozile cu ajutorul calculatorului. Aici vom arăta cum se pot folosi tablourile simple pentru a implementa fiecare dintre aceste structuri.
| |
| == Stive ==
| |
| Operaţia Inserează asupra stivelor este deseori denumită Pune-În-Stivă ( '''Push''' ).
| |
| Operaţia Şterge, care nu cere nici un argument, este deseori numită Scoate-Din-Stivă ( '''Pop''' ).
| |
| Aceste nume sunt aluzii la stivele fizice, ca de exemplu un vraf de farfurii. Ordinea în care sunt luate farfuriile din vraf este ordinea inversă în care au fost introduse în vraf, deoarece doar ultima farfurie este accesibilă.
| |
| O stivă cu cel mult '''n''' elemente poate fi implementată printr-un tablou '''st[0..n-1]'''.
| |
| Tabloul are un atribut '''vf''' care este indicele noii locatii in care se va insera un nou element.
| |
| Stiva constă din elementele st[0..vf-1], unde st[0] este elementul de la baza stivei, iar st[vf-1] este elementul din vârful stivei, ultimul element al stivei.
| |
| Când vf = 0, stiva nu conţine nici un element şi deci este vidă. Se poate testa dacă stiva este vidă prin operaţia de interogare Stivă-Vidă'''( empty ) '''. Dacă se încearcă extragerea (se apelează operaţia Scoate-Din-Stivă) unui element dintr-o stivă vidă, spunem că stiva are depăşire inferioară, care în mod normal este o eroare. Dacă vf depăşeşte valoarea n, stiva are depăşire superioară. (În implementarea noastră nu ne vom pune problema depăşirii stivei.) Fiecare dintre operaţiile stivei pot fi implementate prin doar câteva linii de cod.
| |
|
| |
|
| <syntaxhighlight>
| |
| int st[100], int vf;
| |
| bool Stiva_Vida( ){
| |
| if ( vf == 0 )
| |
| return true;
| |
| return false;
| |
| }
| |
| void Push ( int x ){
| |
| st[vf++] = x;
| |
| }
| |
| int Pop ( ){
| |
| if ( Stiva_Vida () ){
| |
| cout << "nu avem elem in stiva, depasire inferioara";
| |
| return -1;
| |
| }
| |
| vf --;
| |
| return st[vf];
| |
| }
| |
| Fiecare dintre cele trei operaţii asupra stivelor necesită un timp O(1).
| |
|
| |
| </syntaxhighlight>
| |
|
| |
| == Aplicatii cu Stive ==
| |
| ===[https://www.pbinfo.ro/probleme/875/stiva stiva] ===
| |
|
| |
| Să se scrie un program care gestionează o stivă de numere întregi. Inițial stiva este vidă. Programul va citi de la tastatură o listă de operații, care pot fi:
| |
|
| |
| push X – adaugă valoarea întreagă X pe stivă;
| |
| pop – elimină elementul din vârful stivei;
| |
| top – afișează elementul din vârful stivei.
| |
| Programul va realiza asupra stivei operațiile citite, în ordine. Afișările se fac pe ecran, câte o valoare pe linie.
| |
| <syntaxhighlight>
| |
| #include <iostream>
| |
| #include<string.h>
| |
| using namespace std;
| |
|
| |
| int main(){
| |
| int n = 0, nr, x;
| |
| int st[1001];
| |
| cin >> nr;
| |
| char op[20];
| |
| for( int i = 0; i < nr; i++ ){
| |
| cin >> op;
| |
| if( strcmp( op,"push" ) == 0 ){
| |
| cin >> x;
| |
| st[n++] = x;
| |
| }
| |
| else if( strcmp( op, "pop" ) == 0 )
| |
| if ( n > 0 )
| |
| n --;
| |
| else // if(strcmp(op,"top") == 0 )
| |
| if ( n > 0 )
| |
| cout << st[n-1] << "\n";
| |
| }
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| Scris cu functii :
| |
|
| |
| <syntaxhighlight>
| |
| //VARIANTA 2
| |
| #include <iostream>
| |
|
| |
| using namespace std;
| |
|
| |
| const int kMax = 1000;
| |
|
| |
| int stk[kMax + 1];
| |
| int k = 0;
| |
|
| |
| // Verifica daca stiva este vida
| |
| bool empty() {
| |
| if (k == 0) {
| |
| return true;
| |
| } else {
| |
| return false;
| |
| }
| |
| }
| |
|
| |
| // Adauga element in stiva
| |
| void push(int x) {
| |
| stk[k] = x;
| |
| k++;
| |
| }
| |
|
| |
| // Afiseaza varful stivei
| |
| void top() {
| |
| if (!empty()) {
| |
| cout << stk[k - 1] << '\n';
| |
| }
| |
| }
| |
|
| |
| // Sterge varful stivei
| |
| void pop() {
| |
| if (!empty()) {
| |
| k--;
| |
| }
| |
| }
| |
|
| |
| int main() {
| |
| int n;
| |
| cin >> n;
| |
|
| |
| for (int i = 0; i < n; i++) {
| |
| char s[10];
| |
| // citeste un cuvant pana la primul spatiu (sau tab sau enter)
| |
| cin >> s;
| |
|
| |
| if (s[0] == 't') {
| |
| // operatia "top"
| |
| top();
| |
| } else if (s[1] == 'o') {
| |
| // operatia "pop"
| |
| pop();
| |
| } else {
| |
| // operatia "push x"
| |
| int x;
| |
| cin >> x;
| |
| push(x);
| |
| }
| |
| }
| |
|
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| <syntaxhighlight>
| |
| //VARIANTA 2
| |
| #include <iostream>
| |
| #include<string.h>
| |
| using namespace std;
| |
|
| |
| void push ( int st[], int &n, int x ){ // n e nr de elem din stiva
| |
| st[n++] = x;
| |
| }
| |
|
| |
| void pop( int st[], int &n ){
| |
| if ( n > 0 ) // daca avem ce sa scoatem
| |
| n --;
| |
| }
| |
|
| |
| void top( int st[], int n ){
| |
| if ( n > 0 )
| |
| cout << st[n-1] << "\n";
| |
| }
| |
|
| |
| int main(){
| |
| //ifstream fin("date.in");
| |
| int n = 0, nr, x;
| |
| int st[1001];
| |
| cin >> nr;
| |
| char op[20];
| |
| for( int i = 0; i < nr; i++ ){
| |
| cin >> op;
| |
| if( strcmp( op,"push") == 0 ){
| |
| cin >> x;
| |
| push( st, n, x );
| |
| }
| |
| else if( strcmp( op, "pop" ) == 0 )
| |
| pop( st, n );
| |
| else // if(strcmp(op,"top") == 0 )
| |
| top( st, n );
| |
| }
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| <syntaxhighlight>
| |
| // CU STL - STACK
| |
| #include <iostream>
| |
| #include <stack>
| |
| using namespace std;
| |
|
| |
| int main() {
| |
| stack <int> s;
| |
| int c , x;
| |
| string op;
| |
| cin >> c;
| |
| for( int i = 1 ; i <= c ; i++ ) {
| |
| cin >> op;
| |
| if( op == "push") {
| |
| cin >> x;
| |
| s.push(x);
| |
| }
| |
| else if( op == "top" )
| |
| cout << s.top() << '\n';
| |
| else
| |
| s.pop();
| |
| }
| |
| }
| |
| </syntaxhighlight>
| |
| ===[https://www.pbinfo.ro/probleme/848/paranteze1 paranteze1] ===
| |
| Se dau n șiruri de paranteze rotunde. Să se stabilească, despre fiecare șir, dacă este corect parantezat – adică dacă parantezele se închid corect.
| |
| Un șir de paranteze S rotunde este corect parantezat dacă:
| |
| * S este șirul vid, sau
| |
| * S = (T) și T este corect parantezat, sau
| |
| * S = AB, iar A și B sunt corect parantezate.
| |
|
| |
| <syntaxhighlight>
| |
| #include <fstream>
| |
| using namespace std;
| |
|
| |
| ifstream fin( "paranteze1.in" );
| |
| ofstream fout ( "paranteze1.out" );
| |
|
| |
| int main(){
| |
| int n;
| |
| char st[255], c;
| |
| fin >> n;
| |
| fin.get( c );
| |
| for ( int i = 0; i < n; i ++ ) {
| |
| int k = 0;
| |
| c = fin.get( );
| |
| while ( c != '\n' && c!= EOF ) {
| |
| if ( k && st[k-1] == '(' && c == ')' )
| |
| k --;
| |
| else {
| |
| st[k++] = c;
| |
| }
| |
| c = fin.get( );
| |
| }
| |
| fout << ( k == 0 ) << '\n';
| |
| }
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| ===[https://www.pbinfo.ro/probleme/877/cuburi2 cuburi2]===
| |
| Gigel are un set de n cuburi. Fiecare cub este marcat cu un număr natural, de la 1 la n și i se cunoaște lungimea laturii – număr natural. Cu o parte dintre aceste cuburi Gigel va construi o stivă, astfel:
| |
|
| |
| fiecare cub se analizează o singură dată, în ordinea numerelor marcate;
| |
| dacă stiva nu conține niciun cub, cubul curent devine baza stivei
| |
| dacă cubul curent are latura mai mică sau egală cu cubul din vârful stive, se adaugă pe stivă;
| |
| dacă cubul curent are latura mai mare decât cubul din vârful stivei, se vor înlătura de pe stivă cuburi (eventual toate) până când cubul curent are latura mai mică sau egală cu cubul din vârful stivei.
| |
| Să se afișeze numerele de pe cuburile existente la final în stivă, de la bază spre vârf.
| |
| <syntaxhighlight>
| |
| #include <iostream>
| |
|
| |
| using namespace std;
| |
|
| |
| int st[1000], ind[1000];
| |
|
| |
| int main(){
| |
| int n, a;
| |
| cin >> n;
| |
| int k = 0; // cate elem am in stiva
| |
| for( int i = 0; i < n; i++ ) {
| |
| cin >> a;
| |
| while( k > 0 && st[k-1] < a ) // st nu e vida ultima val din stiva => st[k-1]
| |
| k--;
| |
| st[k] = a;
| |
| ind[k] = i;
| |
| k++;
| |
| }
| |
| cout << k << '\n';
| |
| for( int i = 0; i < k; i++ )
| |
| cout << ind[i] + 1 << " ";
| |
|
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| ===[https://www.pbinfo.ro/probleme/2650/books books]===
| |
| <syntaxhighlight>
| |
| #include <iostream>
| |
| using namespace std;
| |
| int v[200000];
| |
| int f[200001];
| |
| int main (){
| |
| int n, i, nr;
| |
| cin >> n;
| |
|
| |
| for ( i = 0; i < n; i++ )
| |
| cin >> v[i];
| |
| int k = -1;
| |
| for ( i = 0; i < n; i++ ) {
| |
| cin >> nr;
| |
| if ( f[nr] ) // dc nr a fost deja pus in ghiozdan
| |
| cout << "0 "; // mut 0 carti
| |
| else { // inaintez in stiva pana gasesc cartea nr
| |
| int cnt = 0;
| |
| do {
| |
| k ++;
| |
| f[v[k]] = 1; // marchez ce carti am pus deja in ghiozdan in verctor de frecventa
| |
| cnt ++;
| |
| } while ( v[k] != nr );
| |
| cout << cnt << " ";
| |
| }
| |
| }
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| ===[https://www.pbinfo.ro/probleme/848/paranteze1 paranteze1]===
| |
| Se dau n șiruri de paranteze rotunde. Să se stabilească, despre fiecare șir, dacă este corect parantezat.
| |
| <syntaxhighlight>
| |
| #include <fstream>
| |
| using namespace std;
| |
|
| |
| ifstream fin( "paranteze1.in" );
| |
| ofstream fout ( "paranteze1.out" );
| |
|
| |
| int main(){
| |
| int n;
| |
| char st[255], c;
| |
| fin >> n;
| |
| fin.get( c );
| |
| for ( int i =0; i < n; i ++ ){
| |
| int k = 0;
| |
| c = fin.get( );
| |
| while ( c != '\n' && c!= EOF ){
| |
| if ( k && st[k-1] == '(' && c == ')' )
| |
| k --;
| |
| else {
| |
| st[k++] = c;
| |
| }
| |
| c = fin.get( );
| |
| }
| |
| fout << ( k == 0 ) << '\n';
| |
| }
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| ===[https://www.pbinfo.ro/probleme/849/paranteze2 paranteze2]===
| |
| Atentie !!! Citirea cu fin.get(c) nu merge. Nu se citeste EOF_ul in c, in schimb functia returneaza EOF.
| |
| <syntaxhighlight>
| |
| #include <fstream>
| |
| using namespace std;
| |
|
| |
| ifstream fin( "paranteze2.in" );
| |
| ofstream fout ( "paranteze2.out" );
| |
|
| |
| int main(){
| |
|
| |
| char st[255], c;
| |
| int k = 0;
| |
| int vmax = 0;
| |
| c = fin.get( );
| |
| while ( c != '\n' && c!= EOF ){
| |
| if ( c == ')' )
| |
| k --;
| |
| else {
| |
| st[k++] = c;
| |
| if ( vmax < k )
| |
| vmax = k;
| |
| }
| |
| c = fin.get( );
| |
| }
| |
| fout << vmax << '\n';
| |
|
| |
| return 0;
| |
| }
| |
|
| |
| </syntaxhighlight>
| |
|
| |
| <syntaxhighlight>
| |
| // CU STL -STACK
| |
| #include <fstream>
| |
| #include <stack>
| |
|
| |
| using namespace std;
| |
|
| |
| bool match(char a, char b) {
| |
| if (a == '(' && b == ')')
| |
| return true;
| |
| if (a == '[' && b == ']')
| |
| return true;
| |
| return false;
| |
| }
| |
|
| |
| int main() {
| |
| ifstream in("paranteze3.in");
| |
| ofstream out("paranteze3.out");
| |
|
| |
| int t;
| |
| bool add;
| |
| string s;
| |
| stack<char> st;
| |
| in >> t;
| |
| while (t--) {
| |
| in >> s;
| |
| while (!st.empty())
| |
| st.pop();
| |
| for (auto c : s) {
| |
| add = true;
| |
| while (!st.empty() && match(st.top(), c)) {
| |
| add = false;
| |
| st.pop();
| |
| if (!st.empty())
| |
| c = st.top();
| |
| }
| |
| if (add)
| |
| st.push(c);
| |
| }
| |
| if (st.empty())
| |
| out << "1\n";
| |
| else
| |
| out << "0\n";
| |
| }
| |
|
| |
| in.close();
| |
| out.close();
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| ===[https://www.pbinfo.ro/probleme/852/paranteze3 paranteze3]===
| |
| Se dau n șiruri de paranteze rotunde sau pătrate. Să se stabilească, despre fiecare șir, dacă este corect parantezat.
| |
| <syntaxhighlight>
| |
| #include <fstream>
| |
| using namespace std;
| |
|
| |
| ifstream fin( "paranteze3.in" );
| |
| ofstream fout ( "paranteze3.out" );
| |
|
| |
| int main(){
| |
| int n;
| |
| char st[255], c;
| |
| fin >> n;
| |
| fin.get( c );
| |
| for ( int i = 0; i < n; i ++ ) {
| |
| int k = 0;
| |
| c = fin.get();
| |
| while ( c != '\n' && c!= EOF ) {
| |
| if ( k && ( st[k-1] == '(' && c == ')' || st[k-1] == '[' && c == ']'))
| |
| k --;
| |
| else {
| |
| st[k++] = c;
| |
| }
| |
| c = fin.get();
| |
| }
| |
| fout << ( k == 0 ) << '\n';
| |
| }
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| ===[https://www.pbinfo.ro/probleme/2650/books books]===
| |
| <syntaxhighlight>
| |
|
| |
| </syntaxhighlight>
| |
| * https://www.varena.ro/problema/betisoare
| |
|
| |
| == Cozi ==
| |
| Vom numi Pune-În-Coadă ( Push ) operaţia de inserare aplicată asupra unei cozi, iar operaţia de stergere o vom numi Scoate-Din-Coadă ( Pop ); asemănător operaţiei Scoate-Din-Stivă aplicată stivei, Scoate-Din-Coadă nu necesită nici un argument.
| |
| Principiul FIFO, propriu cozii, impune ca aceasta să opereze asemănător cu un rând de oameni ce aşteaptă la un ghişeu. Coada are un cap şi o coadă. Când un element este pus în coadă, ocupă locul de la sfârşitul cozii, ca şi un nou venit ce îşi ia locul la coada rândului. Elementul scos din coadă este întotdeauna cel din capul cozii, asemănător persoanei din capul rândului care a aşteptat cel mai mult.
| |
| O modalitate de a implementa o coadă având cel mult n − 1 elemente, foloseste un tablou Q[0..n-1].
| |
| Coada are un atribut '''in''', capul cozii, care conţine indicele capului ei si un atributul '''sf''', sfarsitul cozii, ce conţine indicele noii locaţii în care se va insera în coadă elementul nou venit.
| |
| Elementele din coadă se află în locaţiile cap, cap + 1, ..., coada − 1, iar indicii se parcurg circular, în sensul că locaţia 0 urmează imediat după locaţia n-1. Când cap = coada, coada este goală.
| |
| Iniţial avem in = sf = 0. Când coada este vidă, o încercare de a scoate un element din coadă cauzează o depăşire inferioară în coadă. Când cap = coada + 1, coada este “plină” şi o încercare de a pune în coadă cauzează o depăşire superioară în coadă.
| |
| În Pune-În-Coadă şi Scoate-Din-Coadă, verificarea erorilor de depăşire inferioară a fost omisă.
| |
| <syntaxhighlight>
| |
| const int NMAX = 100;
| |
| int Q[NMAX], in, sf;
| |
|
| |
| void Push ( int x ){
| |
| Q[sf] = x;
| |
| sf = (sf + 1 ) % NMAX;
| |
| }
| |
|
| |
| int Pop () {
| |
| int x = Q[in];
| |
| in = ( int + 1 ) % NMAX;
| |
| return x;
| |
| }
| |
| </syntaxhighlight>
| |
|
| |
| == Exercitii ==
| |
| * Explicaţi cum se pot implementa două stive într-un singur tablou astfel încât nici una dintre stive să nu aibă depăşire superioară, cu excepţia cazului în care numărul total de elemente din ambele stive (împreună) este n. Operaţiile Pune-În-Stivă şi Scoate-Din-Stivă trebuie să funcţioneze într-un timp O(1).
| |
| * Rescrieţi Pune-În-Coadă şi Scoate-Din-Coadă pentru a detecta depăşirile unei cozi.
| |
| * În timp ce stiva permite inserarea şi ştergerea de elemente doar la un singur capăt, iar coada permite inserarea la un capăt şi ştergerea la celălalt capăt, o coadă completă permite
| |
| inserări şi ştergeri la ambele capete. Scrieţi patru proceduri cu timpul de execuţie O(1) pentru
| |
| inserare de elemente şi ştergere de elemente la ambele capete ale unei cozi complete implementată
| |
| printr-un tablou.
| |
| * Arătaţi cum se poate implementa o coadă prin două stive. Analizaţi timpul de execuţie pentru operaţiile cozii.
| |
| * Arătaţi cum se poate implementa o stivă prin două cozi. Analizaţi timpul de execuţie pentru operaţiile stivei.
| |
|
| |
| = Tema Stiva =
| |
| Probleme Pbinfo:
| |
| https://www.pbinfo.ro/probleme/870/depou
| |
| ecuatie1 , Stiva , Cuburi2 , Depou , Paranteze1 , Paranteze4 , Paranteze3 , Paranteze2 , minlex , eval_exp , eval_exp2
| |
|
| |
| Probleme Varena
| |
| * [http://varena.ro/problema/bile2 bile2] dată la concursul .campion 2005
| |
| * [http://varena.ro/problema/turn turn] dată la ONI 2007 clasa a 6<sup>a</sup>
| |
| * [http://varena.ro/problema/paranteze1 paranteze1] dată ca temă la cercul IQ Academy 2018 clasa a 6<sup>a</sup>
| |
| * [http://varena.ro/problema/swap swap] dată la ONI 2013 baraj gimnaziu
| |
|
| |
| Probleme Infoarena
| |
| * [http://infoarena.ro/problema/editor editor]
| |
| * [http://infoarena.ro/problema/trompeta trompeta]
| |
| GREA
| |
| * [http://infoarena.ro/problema/identice identice]
| |
|
| |
| = Bibliografie =
| |
| * Introducere in algoritmi, Thomas Cormen
| |
|
| |
|
| |
|
| |
| = Tema Rezolvari =
| |
| Probleme Varena
| |
| * [http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=382 bile3] dată la concursul .campion 2005
| |
| <syntaxhighlight>
| |
| #include <stdio.h>
| |
| #include <stdlib.h>
| |
| int in[2000], st[2000];
| |
| char out[4000];
| |
| int main(){
| |
| FILE *fin = fopen( "bile2.in","r" );
| |
| FILE *fout = fopen( "bile2.out","w" );
| |
| int i, n, b, kin, kout , k;
| |
|
| |
| fscanf(fin,"%d",&n);
| |
| for(i=0;i<n;i++)
| |
| fscanf(fin,"%d",&in[i]);
| |
|
| |
| kin = 0; //nivel in (zona A)
| |
| k = 0; //nivel stiva (zona B)
| |
| kout = 0; //nivel sol ( in sol voi tine sirul de Intrari/Iesiri )
| |
|
| |
| //citesc pe rand bilele care trebuie sa ajunga in out
| |
| //pentru fiecare bila verific, apas I cata vreme nu am in varful stifei b
| |
| //daca b a ajuns in varful stivei, apas out,
| |
| //daca nu am reusit sa scot bila b, nu are sens sa mai incerc scoarerea celorlalte bile
| |
| //daca am reusit sa scot o bila, atunci valoarea ei, a ramas pe nibelul k al stivei
| |
|
| |
| b = 0; // pentru ca b == st[k] sa fie adevarata la primul pas
| |
| for( i = 0; i < n && b == st[k]; i++ ){
| |
| fscanf( fin,"%d", &b );
| |
| //cat timp mai am bile in in si nu am in varvul stivei val b
| |
| //gasit = 0;
| |
| while( ( kin < n && ( k > 0 && st[k-1] != b ) || k == 0 ) ){
| |
| out[kout++] = 'I'; //apas I
| |
| st[k++] = in[kin]; //mut bila din in in stiva
| |
| kin ++; //avensez in vectorul in
| |
| }
| |
| if( k > 0 && st[k-1] == b ){ //daca stiva nu e vida si in varv am bila potrivita
| |
| out[kout++] = 'O'; //apas o
| |
| k --;
| |
| //gasit = 1; //scad nivelul in stiva
| |
| }
| |
| }
| |
| if( kout == 2*n ) //daca in solutie am 2*n mutari ( n in-uri si n out- uri)
| |
| for( i=0; i < kout; i++ )
| |
| fputc( out[i], fout );
| |
| else
| |
| fprintf(fout,"imposibil");
| |
|
| |
| fclose( fin );
| |
| fclose( fout );
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| * [http://varena.ro/problema/turn turn] dată la ONI 2007 clasa a 6<sup>a</sup>
| |
| <syntaxhighlight>
| |
| </syntaxhighlight>
| |
| * [http://varena.ro/problema/paranteze1 paranteze1] dată ca temă la cercul IQ Academy 2018 clasa a 6<sup>a</sup>
| |
| <syntaxhighlight>
| |
| #include <fstream>
| |
| using namespace std;
| |
|
| |
| ifstream fin( "paranteze1.in" );
| |
| ofstream fout ( "paranteze1.out" );
| |
| const int NMAX = 1000000;
| |
| int main(){
| |
| int n;
| |
|
| |
| char st[NMAX], c;
| |
| int k = 0; // nivelul in stiva
| |
| int kmax = 0; // gradul maxim de imbricare
| |
| c = fin.get();
| |
| while ( c != '\n' ) {
| |
| if ( k && ( st[k-1] == '(' && c == ')' || st[k-1] == '{' && c == '}'))
| |
| k --;
| |
| else {
| |
| st[k++] = c;
| |
| if ( k > kmax )
| |
| kmax = k;
| |
| }
| |
| c = fin.get();
| |
| }
| |
| if ( k )
| |
| fout << -1;
| |
| else
| |
| fout << kmax;
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
| ==== [http://varena.ro/problema/swap swap] dată la ONI 2013 baraj gimnaziu ====
| |
| Pentru calcularea costului parantezarii, vom retine o stiva cu pozitiile parantezelor. Orice paranteza inchisa va inchide ultima paranteza deschisa, pentru care s-a memorat pe stiva pozitia sa i ncadrul vectorului.
| |
| Pentru a optimiza parantezarea, vom incerca sa inchidem o paranteza mai devreme, daca e posibil. Orice swap efectuam va imbunatati costul doar cu 2.
| |
| <syntaxhighlight>
| |
| #include <fstream>
| |
| using namespace std;
| |
|
| |
| ifstream fin( "swap.in" );
| |
| ofstream fout ( "swap.out" );
| |
| const int NMAX = 90000;
| |
| int main(){
| |
| int n;
| |
| int st[NMAX/2];
| |
| char c1, c2;
| |
| int cost = 0; // costul imbricarii
| |
| int nrswap = 0;
| |
| fin >> n;
| |
| c1 = fin.get();
| |
| int k = 0; // nivelul in stiva
| |
| for ( int i = 0; i < n; i ++ ) {
| |
| c2 = fin.get();
| |
| if ( c2 == '(' )
| |
| st[k ++] = i;
| |
| else {
| |
| k -- ;
| |
| cost += ( i - st[k] );
| |
| if ( k > 0 && c1 == '(' ) // daca as fi putut inchide paranteza mai devreme
| |
| nrswap ++;
| |
| }
| |
| c1 = c2;
| |
| }
| |
| fout << cost << '\n';
| |
| if ( nrswap == 0 )
| |
| fout << -1 << '\n';
| |
| else
| |
| fout << cost - 2 << '\n'; // orice swap reduce costul cu 2
| |
| fout << nrswap;
| |
| return 0;
| |
| }
| |
| </syntaxhighlight>
| |
