Bacalaureat 2013 - Problema 4 - Subiectul 3 (Sesiunea speciala)

Fişierul bac.txt conţ ine un şir de cel pu ţin trei şi cel mult 1000000 de numere naturale cu cel mult nouă cifre. Numerele din şir sunt separate prin câte un spa ţiu.
Se cere să se afişeze pe ecran, separate printr-un spa ţiu, două numere distincte, anume cel mai mic număr par cu două cifre şi cel mai mare număr par cu două cifre care NU fac parte din şir.
Dacă nu există două astfel de valori, pe ecran se afisează mesajul Nu exista.
Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al timpului de executare.

Exemplu: dacă fişierul bac.txt con ţine valorile

7 2 40 5 10 15 11 12 18 350

se afişează pe ecran numerele 14 98.

Arată Soluţia

#include <fstream>
#include <iostream>
using namespace std;

ifstream in("bac.txt");

// Vector in care memorez nr pare de 2 cifre gasite in sir
bool pare[45];

int main()
{
    int x, a = 0, b = 0;
    while (in >> x)
    {
        if (x / 100 == 0 && x % 2 == 0) {
            pare[(x - 10) / 2] = true;
        }
    }

    for (int i = 0; i < 45; i++)
        if (pare[i] == false) {
            a = i*2 + 10;
            break;
        }
    for (int i = 44; i >= 0; i--)
        if (pare[i] == false) {
            b = i*2 + 10;
            break;
        }

    if (a == b || a == 0) cout << "Nu exista";
    else cout << a << ' ' << b;

    return 0;
}

Complexitatea algoritmului este `O(n)` (liniar).

Bacalaureat 2013 - Problema 3 - Subiectul 3 (Sesiunea speciala)

Se consideră subprogramul sub, cu trei parametri:

• n, prin care primeşte un număr natural (2<n<50);
• v, prin care primeşte un tablou unidimensional cu n elemente, numere naturale cu cel mult 4 cifre;
• x, prin care primeşte un număr natural cu cel mult 4 cifre. Cel pu ţin unul dintre elementele tabloului are valoarea x.

Subprogramul modifică ordinea valorilor din tablou, astfel încât toate valorile egale cu x să ocupe primele poziţ ii din v, iar celelalte valori să se regăsească în continuarea acestora.
Tabloul modificat este furnizat tot prin parametrul v.
Scrie ţi defini ţia completă a subprogramului.

Exemplu: dacă n=9, v=(2, 1, 0, 1, 7, 0, 1, 4, 5) şi x=1, atunci, după apel, o soluţ ie posibilă este v=(1, 1, 1, 2, 0, 7, 0, 4, 5).

Arată Soluţia

void sub(int n, int v[], int x)
{
    for (int i = 0; i < n; i++)
    {
        if (v[i] == x) {
            int j;
            for (j = i-1; j >= 0 && v[j] != x; j--); // instr. vida
            v[i] = v[j+1];
            v[j+1] = x;
        }
    }
}

Bacalaureat 2013 - Problema 5 - Subiectul 2 (Sesiunea speciala)

Se consideră un text cu cel mult 100 de caractere (litere mici ale alfabetului englez şi spaţ ii), în care cuvintele sunt separate prin câte un spaţ iu. Înaintea primului cuvânt şi după ultimul cuvânt nu există spa ţii.
Scrieţ i un program C/C++ care citeşte de la tastatură un text de tipul men ţionat mai sus şi determină transformarea acestuia în memorie prin înlocuirea fiecărui cuvânt format din trei litere cu simbolul *. Programul afişează pe ecran textul ob ţinut.

Exemplu: pentru textul

bun este izvorul ce are apa rece

se afişează

* este izvorul ce * * rece

Algoritmul reţine adresa de început a fiecărui cuvânt şi numără numărul de litere din fiecare cuvânt până când întâlneşte un caracter spaţiu.
Aici se verifică dacă a fost întâlnit un cuvânt de 3 litere, caz în care se deplasează tot şirul spre stânga, iar pe prima poziţie din cuvânt se inserează caracterul *.
Indiferent dacă a fost găsit un cuvânt de 3 litere, după fiecare spaţiu începe un nou cuvânt ceea ce înseamnă că start este actualizat, iar cnt este resetat.

Arată Soluţia

#include <iostream>
#include <cstring>
using namespace std;

// Deplaseaza sirul spre stanga cu 2 unitati
void shift(char* p, int& l, int& start)
{
    for (int i = start; i <= l; i++)
        p[i-2] = p[i];
    l -= 2;
    start -= 2;
}

int main()
{
    char txt[101];
    cin.get(txt, 101);
    // cnt - numara literele unui cuvant
    // start - memoreaza pozitia de inceput a unui cuvant
    // l - memoreaza lungimea sirului
    int cnt = 0, start = 0, l = strlen(txt);
    for (int i = 0; i < l; i++)
    {
        if (txt[i] != ' ') cnt++;
        else {
            if (cnt == 3)
            {
                txt[start] = '*';
                shift(txt, l, i);
            }
            cnt = 0; start = i+1;
        }
    }
    cout << txt;
    return 0;
}

Bacalaureat 2011 - Problema 4 - Subiectul 3 (Sesiunea iunie-iulie)

Se citesc de la tastatură două numere naturale s1 si s2 (0<s1≤18, 0≤s2≤18) si se cere scrierea în fisierul BAC.TXT, fiecare pe câte o linie, în ordine strict crescătoare, a tuturor numerelor naturale cu exact 5 cifre, pentru care suma primelor două cifre este egală cu s1, iar suma ultimelor două cifre este egală cu s2. Pentru determinarea numerelor indicate se utilizează un algoritm eficient din punct de vedere al timpului de executare.

Exemplu: dacă s1=8, iar s2=7, atunci 35725 este unul dintre numerele care respectă proprietatea cerută (3+5=8 si 2+5=7).

Arată Soluţia

#include <iostream>
#include <fstream>
using namespace std;

ofstream fout("BAC.txt");

int main()
{
    int s1, s2;
    cin >> s1 >> s2;
    int c1, c2, c3, c4, c5; // Cele cinci cifre care alcatuiesc numerele cerute
    int l1, l2;             // Limitele iteratiilor (veti vedea imediat ce vreau sa spun)
    
    if(s1 > 9) l1 = 9;
    else l1 = s1;
    if(s2 > 9) l2 = 9;
    else l2 = s2;

    for(c1 = 1; c1 <= l1; c1++) // Prima cifra nu poate fi zero
    {
        c2 = s1 - c1;
        if(c2 > 9) continue; // O cifra nu poate fi un numar de doua cifre
        for(c3 = 0; c3 <= 9; c3++) // Cifra din mijloc va fi mereu intre 0 si 9
        {
            for(c4 = 0; c4 <= l2; c4++)
            {
                c5 = s2 - c4;
                if(c5 > 9) continue;
                fout << c1 * 10000 + c2 * 1000 + c3 * 100 + c4 * 10 + c5 << '\n';
            }
        }
    }

    return 0;
}

Bacalaureat 2011 - Problema 3 - Subiectul 3 (Sesiunea iunie-iulie)

Subprogramul inserare are doi parametri:

• n, prin care primeste un număr natural (2≤n≤20);
• a, prin care primeste un tablou unidimensional care memorează un sir de n numere naturale, fiecare cu cel mult 4 cifre. Cel puţin un element al tabloului este număr par.

Subprogramul modifică tabloul astfel încât după fiecare termen par al sirului inserează valoarea 2011 si furnizează, tot prin parametrii n si a, valorile actualizate ale datelor primite.
Scrieţi în limbajul C/C++ definiţia completă a subprogramului.

Exemplu: dacă n=7 si a=(1,4,5,3,82,6,2) atunci, după apel,

n=11 si a=(1,4,2011,5,3,82,2011,6,2011,2,2011).

Arată Soluţia

Soluţia acestei probleme este similară cu soluţia Problemei 3, Subiectul 3, Bacalaureat 2012.

void inserare(int& n, int a[])
{
    for(int i = 0; i < n; i++)
    {
        if(a[i] % 2 == 0)
        {
            for(int j = n; j > i+1; j--)
                a[j] = a[j-1];
   
            a[i+1] = 2011;
            ++n; ++i;
        }
    }
}

Bacalaureat 2011 - Problema 5 - Subiectul 2 (Sesiunea iunie-iulie)

Scrieţi un program C/C++ care citeşte de la tastatură un număr natural n (2≤n≤20) si apoi n cuvinte distincte, fiecare fiind format din cel mult 20 de caractere, numai litere mici ale alfabetului englez. La introducerea datelor, după fiecare cuvânt se tastează Enter. Programul afişează pe ecran numărul de cuvinte dintre ultimele n-1 citite, care încep cu primul cuvânt citit.

Exemplu: dacă n=5 şi cuvintele citite sunt:

bun
buncar
bunici
abundent
bunavoie

pe ecran se afişează 3 (deoarece numai cuvintele buncar, bunici şi bunavoie încep cu bun).

Arată Soluţia

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int n, count = 0, len; char first[21], word[21];
    
    cin >> n; cin.get();
    cin.getline(first, 21);
    len = strlen(first); // Memorez lungimea primului cuvant

    for(int i = 2; i <= n; i++)
    {
        cin.getline(word, 21);
        // Verifica daca are ca prefix pe first
        int j = 0;
        for(; (j < len) && (first[j] == word[j]); j++); // ATENTIE! Instructiune vida!

        if(j == len) ++count;
    }
    cout << count; // Afisez numarul de cuvinte
    
    return 0;
}

Bacalaureat 2012 - Problema 4 - Subiectul 3 (Sesiunea speciala)

Fişierul bac.txt conţine pe prima linie un număr natural par n cu cel mult patru cifre, iar pe următoarea linie un şir de n numere naturale cu cel mult nouă cifre. Numerele din şir sunt în ordine crescătoare şi sunt separate prin câte un spaţiu. Se cere să se afişeze pe ecran cel mai mare număr din prima jumătate a şirului care să fie strict mai mic decât oricare număr din a doua jumătate a şirului. Dacă în fişier nu se află o astfel de valoare, pe ecran se afişează mesajul Nu exista. Pentru determinarea numărului cerut se utilizează un algoritm eficient din punctul de vedere al memoriei şi al timpului de executare.

Exemplu: dacă fişierul bac.txt are conţinutul

30
1 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 7 10

atunci pe ecran se afişează 3, iar dacă fişierul are conţinutul

6
3 3 3 3 9 15

atunci pe ecran se afişează Nu exista.

Arată Soluţia

Voi folosi variabilele x şi y pentru a reţine ultimele valori distincte citite din fişier, iar variabila r pentru valoarea curentă citită din fişier.
Ideea este să găsim ultimele două valori distincte (dacă există) din prima jumătate a şirului, şi să le comparăm cu prima valoare din a doua jumătate a şirului. În funcţie de rezultat, conform cerinţei problemei, vom afişa mesajele corespunzătoare.

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("bac.txt");

int main()
{
    int n, x, y, r;
    fin >> n;
    fin >> r; x = y = r;
    for(int i = 2; i <= (n/2 + 1); i++)
    {
        fin >> r;
        if(i == (n/2 + 1)) 
        {
            if(y < r) cout << y;
            else if(x < r) cout << x;
            else cout << "Nu exista";
        }
        else if(r != y) { x = y; y = r; }
    }
    return 0;
}

Bacalaureat 2012 - Problema 3 - Subiectul 3 (Sesiunea speciala)

Se consideră subprogramul minus, cu doi parametri:

• n, prin care primeşte o valoare naturală 2 < n < 50;
• v, prin care primeşte un tablou unidimensional cu n elemente, numere întregi cu cel mult 4 cifre.

Cel puţin unul dintre elementele tabloului este nenul.
După fiecare element nenul din tablou, subprogramul inserează câte un nou element, cu aceeaşi valoare absolută, dar cu semn opus, ca în exemplu. Tabloul modificat, precum şi valoarea actualizată a lui n, sunt furnizate tot prin parametrii v, respectiv n. Scrieţi în limbajul C/C++ definiţia completă a subprogramului.

Exemplu: dacă n=5 şi v=(4, -5, 0, 9, 0), atunci după apel n=8, iar v=(4, -4, -5, 5, 0, 9, -9, 0).

Arată Soluţia

// Valoarea lui n actualizata este furnizata prin parametru
// Deci trebuie sa fie de tip referinta
void minus(int& n, int v[])
{
    for(int i = 0; i < n; i++)
    {
        if(v[i] != 0)
        {
            // Deplasez vectorul spre dreapta ca sa fac loc pentru insertie
            for(int j = n; j > i+1; j--) 
                v[j] = v[j-1];
                
            v[i+1] = v[i] * (-1);
            ++n; ++i; // Sar peste v[i+1]
        }
    }
}

Bacalaureat 2012 - Problema 5 - Subiectul 2 (Sesiunea speciala)

Scrieţi un program C/C++ care citeşte de la tastatură două cuvinte distincte, fiecare fiind format din cel mult 30 de caractere, numai litere mici ale alfabetului englez. După primul cuvânt se tastează Enter. Programul verifică dacă prin eliminarea unor litere din cel de al doilea cuvânt se poate obţine primul cuvânt. În caz afirmativ programul afişează pe ecran mesajul DA, altfel mesajul NU.
Exemple: dacă se citesc, în această ordine, cuvintele:

calut
bacalaureat

pe ecran se afişează mesajul DA
iar dacă se citesc, în această ordine, cuvintele:

calut
lacatus

pe ecran se afişează mesajul NU.

Arată Soluţia

Voi parcurge al doilea cuvând (word2), şi voi compara fiecare literă a acestuia cu prima literă din primul cuvânt (word1). Dacă se potrivesc, incrementez indicele k cu 1 (ca să trec la următoarea literă din primul cuvânt). Repet aceşti paşi până când ajung la sfârşitul lui (word2).
Dacă primul cuvânt se poate obţine prin eliminarea unor litere din al doilea cuvânt, înseamnă că atunci când voi ajunge la ultima literă din (word1), se va potrivi cu o literă din (word2), şi k va fi incrementat, iar word1[k] va fi '\0'.

#include <iostream>
using namespace std;

int main()
{
    // Declarare variabile
    char word1[31], word2[31];
    // Citire de la tastatura
    cin.getline(word1, 31);
    cin.getline(word2, 31);
    // Algoritm de rezolvare
    int k = 0; // Pozitia in word1
    for(int i = 0; word2[i] != '\0' && word1[k] != '\0'; i++)
        if(word2[i] == word1[k]) ++k;
    
    if(word1[k] == '\0') cout << "DA";
    else cout << "NU";
    
    return 0;
}

Puteţi descărca soluţia de aici.