Rezolvare BAC Informatică 2025 — Simulare națională, Varianta simulare

Subiectul I, 1 (4 p)

Cerința, pe scurt: Valoarea expresiei C/C++ 3+7/4+3. Variante: 1, 5.5, 7, 7.75.

Ce se cere: Să aplici prioritatea operatorilor și împărțirea întreagă.

Noțiuni: prioritatea lui / față de + · împărțirea întreagă între int-uri

Rezolvare pas cu pas

1. / are prioritate mai mare decât +, deci se calculează întâi 7/4.
2. 7 și 4 sunt int, deci 7/4 = 1 (partea fracționară se pierde).
3. 3 + 1 + 3 = 7.

Răspuns final: c — 7

Verificare: Expresia a fost evaluată exact așa într-un program C++: 7.

Subiectul I, 2 (4 p)

Cerința, pe scurt: struct interval { float s,d; } v[20]; — expresia care reprezintă extremitatea stângă a primului interval.

Ce se cere: Să accesezi un câmp al unui element dintr-un tablou de structuri.

Noțiuni: tablou de structuri · operatorul . · indexarea de la 0

Rezolvare pas cu pas

1. Tabloul se numește v; primul element este v[0].
2. Câmpul extremității stângi este s, deci expresia este v[0].s.
3. s.v[0] și s(0).v nu au sens (s este un câmp, nu o variabilă); v(0) nu este sintaxa de indexare în C/C++.

Răspuns final: a — v[0].s

Verificare: Declarația din enunț și expresia v[0].s au fost compilate și folosite într-un program C++.

Subiectul I, 3 (4 p)

Cerința, pe scurt: Arbore cu 50 de noduri, rădăcina 1, tatăl nodului i este [i/2]. Lungimea lanțului dintre nodurile 14 și 47.

Ce se cere: Să urci din fiecare nod spre rădăcină până la primul strămoș comun și să numeri muchiile.

Noțiuni: arbore cu rădăcină · vectorul de tați · lungimea unui lanț = numărul de muchii

Rezolvare pas cu pas

1. Din 47 urcăm: 47 → 23 → 11 → 5 → 2 → 1 (5 muchii).
2. Din 14 urcăm: 14 → 7 → 3 → 1 (3 muchii).
3. Primul nod comun este rădăcina 1, deci lanțul este 14, 7, 3, 1, 2, 5, 11, 23, 47.
4. Lungimea: 5 + 3 = 8 muchii.

Răspuns final: b — 8

Verificare: Program C++: urcare simultană până la strămoșul comun (1) și calcul cu adâncimile nodurilor: 8.

Subiectul I, 4 (4 p)

Cerința, pe scurt: f(n) întoarce (n%2)*(n%10)+f(n/10) pentru n≠0 și 0 pentru n=0. Valoarea lui f(1234).

Ce se cere: Să observi că f adună cifrele impare ale lui n.

Noțiuni: recursivitate · n%2 este 1 pentru cifră impară, 0 pentru pară

Rezolvare pas cu pas

1. (n%2)*(n%10) este ultima cifră dacă n e impar (ultima cifră e impară) și 0 altfel — deci f adună cifrele impare.
2. f(1234) = 0 + f(123) = 3 + f(12) = 3 + 0 + f(1) = 3 + 1 + f(0) = 4.

Răspuns final: b — 4

Verificare: Funcția din enunț a fost rulată în C++: f(1234) = 4.

Subiectul I, 5 (4 p)

Cerința, pe scurt: Graf neorientat cu 7 noduri și 21 de muchii. Numărul minim de muchii de eliminat ca graful parțial să aibă două componente conexe, fiecare cu cel puțin două noduri.

Ce se cere: Să recunoști graful complet și să alegi împărțirea care taie cele mai puține muchii.

Noțiuni: graf complet: n(n−1)/2 muchii · componentă conexă · graf parțial

Rezolvare pas cu pas

1. 7 · 6 / 2 = 21, deci graful este complet: oricare două noduri sunt unite printr-o muchie.
2. Dacă cele două componente au k și 7 − k noduri, trebuie eliminate toate cele k(7 − k) muchii dintre ele (în interiorul fiecărei grupe graful rămâne complet, deci conex).
3. Cu k ≥ 2 și 7 − k ≥ 2: k = 2 → 10, k = 3 → 12. Minimul este 10.

Răspuns final: c — 10

Verificare: Forță brută în C++ peste toate cele 2²¹ grafuri parțiale: minimul de muchii eliminate pentru exact două componente conexe cu cel puțin două noduri fiecare este 10.

Subiectul al II-lea, 1a (6 p)

Cerința, pe scurt: Pentru fiecare x de la n la m, dacă x ≥ 2, se caută cel mai mic divizor a ≥ 2 al lui x; dacă a = x, b crește. Se afișează b. Ce se afișează pentru n = 20, m = 30?

Ce se cere: Să recunoști ce numără algoritmul și să aplici pe intervalul dat.

Noțiuni: cel mai mic divizor propriu · număr prim

Rezolvare pas cu pas

1. Bucla cât timp se oprește la cel mai mic divizor a ≥ 2 al lui x. Acesta este chiar x doar dacă x este prim.
2. Deci algoritmul numără numerele prime din [n, m].
3. În [20, 30] numerele prime sunt 23 și 29.

Răspuns final: Se afișează 2.

Verificare: Programul C++ de la punctul c, rulat cu 20 și 30, afișează 2; numărarea primelor din [20, 30] făcută separat în Python dă tot 2.

Subiectul al II-lea, 1b (6 p)

Cerința, pe scurt: Cele mai mici două valori întregi pozitive pentru n astfel încât, cu m = 22, să se afișeze 2.

Ce se cere: Intervalul [n, 22] trebuie să conțină exact două numere prime.

Noțiuni: numere prime ≤ 22

Rezolvare pas cu pas

1. Primele până la 22 sunt 2, 3, 5, 7, 11, 13, 17, 19.
2. Exact două prime în [n, 22] înseamnă 17 și 19, deci 13 < n ≤ 17.
3. Cele mai mici două valori: 14 și 15.

Răspuns final: 14 și 15

Verificare: Am rulat programul pentru toate n de la 1 la 22 cu m = 22: afișează 2 exact pentru n = 14, 15, 16, 17.

Subiectul al II-lea, 1c (10 p)

Cerința, pe scurt: Scrieți programul C/C++ corespunzător algoritmului dat.

Ce se cere: Transcriere fidelă: citire, for, if-uri imbricate, while, afișare.

Noțiuni: for · while · if imbricat

Rezolvare pas cu pas

1. pentru x←n,m devine for (x = n; x <= m; x++).
2. Al doilea dacă este în interiorul primului, deci ambele instrucțiuni stau în blocul lui if (x >= 2).

#include <iostream>
using namespace std;
int main()
{
    int n, m, b = 0, x, a;
    cin >> n >> m;
    for (x = n; x <= m; x++)
        if (x >= 2)
        {
            a = 2;
            while (x % a > 0)
                a = a + 1;
            if (x == a)
                b = b + 1;
        }
    cout << b;
    return 0;
}

Complexitate: O((m − n) · m) în cel mai rău caz — pentru fiecare x se caută divizorul liniar.

Răspuns final: Programul de mai sus.

Verificare: Compilat fără avertismente (g++ -Wall -Werror) și rulat: 20 30 → 2.

Subiectul al II-lea, 1d (6 p)

Cerința, pe scurt: Scrieți în pseudocod un algoritm echivalent, înlocuind structura pentru...execută cu o structură repetitivă de alt tip.

Ce se cere: O buclă cât timp cu inițializare înainte și incrementare la final.

Noțiuni: echivalența pentru ↔ cât timp · structură cu test inițial

Rezolvare pas cu pas

1. Inițializarea contorului (x ← n) se mută înaintea buclei.
2. Condiția de continuare este x ≤ m; testul fiind inițial, pentru n > m bucla nu s-ar executa (ca și for-ul).
3. Incrementarea x ← x+1 se pune ultima în corpul buclei.

citește n,m (numere naturale, n≤m)
b←0
x←n
┌cât timp x≤m execută
│ ┌dacă x>=2 atunci
│ │ a←2
│ │ ┌cât timp x%a>0 execută
│ │ │ a←a+1
│ │ └■
│ │ ┌dacă x=a atunci
│ │ │ b←b+1
│ │ └■
│ └■
│ x←x+1
└■
scrie b

Răspuns final: Algoritmul echivalent de mai sus.

Verificare: Transcrierea în C++ a acestui algoritm a dat aceeași ieșire ca programul original pentru toate perechile 0 ≤ n ≤ m, cu n ≤ 40 și m ≤ 45.

Subiectul al II-lea, 2 (6 p)

Cerința, pe scurt: Declarați variabila s (2 sportivi: vârstă și înălțime naturale de cel mult 3 cifre, greutate reală cu două zecimale), folosită ca s[0].varsta, s[0].inaltimea, s[1].greutatea, și scrieți secvența care afișează înălțimea sportivului mai tânăr; la vârstă egală, a celui cu greutatea mai mică.

Ce se cere: Un tablou de 2 structuri și o decizie în trei pași.

Noțiuni: struct · tablou de structuri · if…else if

Rezolvare pas cu pas

1. Expresiile s[0].varsta și s[1].greutatea arată că s este un tablou de 2 structuri cu câmpurile varsta, inaltimea (int) și greutatea (float).
2. Comparăm întâi vârstele; doar dacă sunt egale comparăm greutățile.
3. În programul de mai jos, declarația este structura de deasupra lui main, iar secvența cerută este blocul de if-uri; citirea este doar pentru testare.

#include <iostream>
using namespace std;
struct
{
    int varsta, inaltimea;
    float greutatea;
} s[2];
int main()
{
    cin >> s[0].varsta >> s[0].inaltimea >> s[0].greutatea;
    cin >> s[1].varsta >> s[1].inaltimea >> s[1].greutatea;
    if (s[0].varsta < s[1].varsta)
        cout << s[0].inaltimea;
    else if (s[1].varsta < s[0].varsta)
        cout << s[1].inaltimea;
    else if (s[0].greutatea < s[1].greutatea)
        cout << s[0].inaltimea;
    else
        cout << s[1].inaltimea;
    return 0;
}

Răspuns final: Declarația și secvența de mai sus.

Verificare: Rulat pe patru cazuri: primul mai tânăr, al doilea mai tânăr, vârste egale cu fiecare dintre sportivi mai ușor — de fiecare dată s-a afișat înălțimea corectă.

Subiectul al II-lea, 3 (6 p)

Cerința, pe scurt: Completați secvența for(i=0;i<6;i++) for(j=0;j<6;j++) … (fără alte variabile, cel mult 6 atribuiri) astfel încât tabloul a (6×6, inițial nul) să devină cel din enunț: prima și ultima linie pline cu 1, respectiv 6, iar pe liniile 1–4 valoarea i+1 pe coloanele 0, 1, 4, 5 și 0 pe coloanele 2, 3.

Ce se cere: O condiție care descrie pozițiile nenule și valoarea lor.

Noțiuni: tablou bidimensional · condiții pe indici

Rezolvare pas cu pas

1. Pe fiecare poziție nenulă valoarea este numărul liniei plus 1: i + 1.
2. Pozițiile nenule: linia 0, linia 5 și coloanele 0, 1, 4, 5 (j < 2 sau j > 3).
3. Restul rămân 0, cum erau inițial — nu e nevoie de atribuire. Folosim o singură atribuire.

    for(i=0;i<6;i++)
        for(j=0;j<6;j++)
            if (i == 0 || i == 5 || j < 2 || j > 3) a[i][j] = i + 1;

Răspuns final: Secvența de mai sus.

Verificare: Secvența a fost rulată pe un tablou inițial nul; tabloul afișat coincide linie cu linie cu cel din enunț.

Subiectul al III-lea, 1 (10 p)

Cerința, pe scurt: Subprogramul zero(a, n, imp): a are cel mult 100 de numere întregi; imp = numărul de valori impare; returnează numărul de zerouri în care se termină produsul valorilor. Exemplu: (2, 25, 7, 6, 15, 9, 8) → imp = 4, returnează 3.

Ce se cere: Numărarea imparelor și a zerourilor finale ale produsului, fără a calcula produsul.

Noțiuni: 10 = 2 · 5 · descompunere în factori · transmitere prin referință

Rezolvare pas cu pas

1. Produsul a până la 100 de numere depășește orice tip întreg, deci nu îl calculăm.
2. Fiecare zero final provine dintr-un factor 10 = 2 · 5. Numărăm de câte ori apar 2 și 5 în toate valorile; numărul de zerouri este minimul celor două.
3. Pentru numere negative lucrăm cu valoarea absolută; testul de imparitate a[i] % 2 != 0 funcționează și pentru ele.
4. Dacă vectorul conține un 0, produsul este 0, care se scrie cu o singură cifră 0 (enunțul nu tratează explicit cazul; am ales această convenție).
5. Exemplu: 2 (2¹), 25 (5²), 6 (2¹), 15 (5¹), 8 (2³) → 2⁵ și 5³ → 3 zerouri; impare: 25, 7, 15, 9 → imp = 4.

int zero(int a[], int n, int &imp)
{
    int i, x, d2 = 0, d5 = 0;    // de câte ori apar factorii 2 și 5 în produs
    bool areZero = false;
    imp = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] % 2 != 0)       // merge și pentru numere negative
            imp++;
        if (a[i] == 0)
            areZero = true;
        else
        {
            x = a[i] < 0 ? -a[i] : a[i];
            while (x % 2 == 0) { d2++; x = x / 2; }
            while (x % 5 == 0) { d5++; x = x / 5; }
        }
    }
    if (areZero)
        return 1;                // produsul este 0, scris cu o singură cifră 0
    return d2 < d5 ? d2 : d5;    // fiecare zero final = o pereche 2·5
}

Complexitate: O(n · log V), unde V este cea mai mare valoare absolută; memorie O(1).

Răspuns final: Subprogramul de mai sus.

Verificare: Rulat pe exemplul din enunț (4 3), pe 1000 (0 3), pe valori negative și pe un vector cu 0; apoi pe 300 de vectori aleatori de până la 100 de elemente, comparați cu produsul calculat exact (întregi nelimitați) în Python.

Subiectul al III-lea, 2 (10 p)

Cerința, pe scurt: Un cuvânt e muzical dacă conține o notă din {do, re, mi, fa, sol, la, si}. Textul (cel mult 200 de caractere, litere mici, cuvinte separate prin spații și/sau virgule) se citește de la tastatură; se afișează numărul de cuvinte muzicale și cuvântul cu cele mai multe note distincte. Exemplu: „la orele de muzica fredonam doine, balade, solfegii si cantece remixate” → 8 fredonam (sau 8 remixate).

Ce se cere: Împărțirea textului în cuvinte și căutarea fiecărei note în fiecare cuvânt.

Noțiuni: cin.getline · strtok cu mai mulți separatori · strstr · strcpy

Rezolvare pas cu pas

1. Citim tot rândul cu cin.getline (cin >> s s-ar opri la primul spațiu).
2. strtok(text, " ,") separă cuvintele după spații și virgule, oricâte ar fi consecutive.
3. Pentru fiecare cuvânt numărăm notele distincte conținute: pentru fiecare dintre cele 7 note, strstr spune dacă apare.
4. Cuvântul e muzical dacă numărul este cel puțin 1; reținem primul cuvânt cu numărul maxim (comparație strictă).
5. Pe exemplu: muzicale sunt la, orele, fredonam, doine, balade, solfegii, si, remixate (8); fredonam (re, do) și remixate (re, mi) au câte 2 note, fredonam apare primul.

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    char text[201], cel[201] = "", *p;
    const char note[7][4] = {"do", "re", "mi", "fa", "sol", "la", "si"};
    int nr = 0, maxim = 0, k, c;
    cin.getline(text, 201);
    p = strtok(text, " ,");
    while (p != NULL)
    {
        c = 0;                       // câte note distincte conține cuvântul p
        for (k = 0; k < 7; k++)
            if (strstr(p, note[k]) != NULL)
                c++;
        if (c > 0)
            nr++;
        if (c > maxim)
        {
            maxim = c;
            strcpy(cel, p);
        }
        p = strtok(NULL, " ,");
    }
    cout << nr;
    if (nr > 0)
        cout << ' ' << cel;
    return 0;
}

Complexitate: O(L · 7), unde L este lungimea textului; memorie pentru două șiruri de 201 caractere.

Răspuns final: Programul de mai sus.

Verificare: Rulat pe exemplul din enunț (8 fredonam), pe text cu virgule și spații multiple, pe text fără cuvinte muzicale și pe 200 de texte aleatoare, comparate cu o implementare separată în Python.

Subiectul al III-lea, 3 (10 p)

Cerința, pe scurt: În minutul k laserul emite semnalele de culori 1, 2, …, k, deci șirul este 1 12 123 1234 … După m minute (m ≤ 10⁶, din BAC.IN), se cere culoarea celui de-al n-lea semnal (n ≤ 10⁹): „OK culoare” sau „EROARE” dacă nu a fost emis. Exemplu: m=5, n=14 → OK 4; m=5, n=24 → EROARE. Algoritm eficient în timp și memorie.

Ce se cere: a) descrierea algoritmului și de ce e eficient; b) programul.

Noțiuni: sume 1 + 2 + … + k = k(k+1)/2 · simulare fără tablouri · long long

Rezolvare pas cu pas

1. După k minute s-au emis s = 1 + 2 + … + k semnale. Semnalul n este emis în primul minut k pentru care s ≥ n.
2. În acel minut, înainte de el s-au emis s − k semnale, deci semnalul n este al n − (s − k)-lea din grupul 1, 2, …, k — adică are culoarea n − (s − k).
3. a) Pornim cu k = 1, s = 1 și, cât timp s < n și k < m, trecem la minutul următor (k crește, s crește cu k). Dacă la final tot s < n, semnalul nu a fost emis: EROARE; altfel afișăm OK n − (s − k). Nu memorăm șirul (memorie O(1)); bucla face cel mult min(m, √(2n) + 1) pași, adică sub 44 722 de pași pentru n ≤ 10⁹, indiferent cât de mare e m.
4. Pe exemplu: s ia valorile 1, 3, 6, 10, 15; la k = 5, s = 15 ≥ 14, culoarea este 14 − (15 − 5) = 4.
5. s depășește n cu cel mult k, dar folosim long long ca să nu existe nicio grijă de depășire.

#include <fstream>
#include <iostream>
using namespace std;
int main()
{
    ifstream fin("BAC.IN");
    long long m, n, k = 1, s = 1;    // s = câte semnale s-au emis până la finalul minutului k
    fin >> m >> n;
    while (s < n && k < m)
    {
        k++;
        s = s + k;                   // în minutul k se emit k semnale
    }
    if (s < n)
        cout << "EROARE";
    else
        cout << "OK " << n - (s - k);  // poziția lui n în grupul 1 2 ... k
    fin.close();
    return 0;
}

Complexitate: Timp O(min(m, √n)), memorie O(1).

Răspuns final: Programul de mai jos (pentru m=5, n=14 afișează OK 4; pentru m=5, n=24 afișează EROARE).

Verificare: Rulat pe cele două exemple din enunț, pe cazurile limită (ultimul semnal emis, primul neemis, m = 1), pe toate perechile cu m ≤ 30 comparate cu șirul construit efectiv în Python și pe m = 10⁶, n = 10⁹ comparat cu o formulă închisă.