Rezolvare BAC Informatică 2026 — Sesiunea iunie–iulie, Varianta 4

Subiectul I, 1 (4 p)

Cerința, pe scurt: Indicați expresia C/C++ a cărei valoare este 26: (2026-26)/100, 2026/100, (2026-26)%100, 2026%100.

Ce se cere: Să calculezi fiecare expresie cu regulile împărțirii întregi din C/C++.

Noțiuni: împărțirea întreagă / între int-uri · restul împărțirii %

Rezolvare pas cu pas

1. (2026-26)/100 = 2000/100 = 20.
2. 2026/100 = 20 (partea fracționară se pierde la împărțirea întreagă).
3. (2026-26)%100 = 2000%100 = 0.
4. 2026%100 = 26 — restul împărțirii lui 2026 la 100 sunt ultimele două cifre.

Răspuns final: d — 2026%100

Verificare: Am evaluat cele patru expresii într-un program C++: 20, 20, 0, 26.

Subiectul I, 2 (4 p)

Cerința, pe scurt: Subprogramul f(n,m) returnează 0 dacă n≥m, altfel 1+f(n+1,m-2). Indicați f(1,10).

Ce se cere: Să urmărești apelurile recursive până la condiția de oprire.

Noțiuni: recursivitate · condiție de oprire

Rezolvare pas cu pas

1. f(1,10): 1<10 → 1 + f(2,8)
2. f(2,8): 2<8 → 1 + f(3,6)
3. f(3,6): 3<6 → 1 + f(4,4)
4. f(4,4): 4≥4 → 0. Adunăm: 1+1+1+0 = 3.

Răspuns final: b — 3

Verificare: Funcția a fost rulată în C++: f(1,10) = 3.

Subiectul I, 3 (4 p)

Cerința, pe scurt: Backtracking pe pachete (Clisura Dunării, munte, litoral), cu mulțimile ordonate date. Ce pachet se generează imediat înainte de (Șvinița, Bușteni, Venus)?

Ce se cere: Să recunoști produsul cartezian generat în ordine lexicografică și să faci un pas înapoi.

Noțiuni: backtracking · produs cartezian · ordine lexicografică

Rezolvare pas cu pas

1. Exemplul din enunț arată că ultima componentă variază cel mai repede: Venus, Neptun, Olimp; apoi se schimbă destinația de munte.
2. (Șvinița, Bușteni, Venus) este primul pachet care începe cu Șvinița: munte = primul (Bușteni), litoral = primul (Venus).
3. Deci înaintea lui vine ultimul pachet care începe cu destinația precedentă, Eșelnița: munte = ultimul (Predeal), litoral = ultimul (Olimp).

Răspuns final: b — (Eșelnița, Predeal, Olimp)

Verificare: Am generat toate cele 27 de pachete în ordine și am citit elementul dinaintea lui (Șvinița, Bușteni, Venus).

Subiectul I, 4 (4 p)

Cerința, pe scurt: Graf orientat cu 4 vârfuri, dat prin matricea de adiacență (linii: 0110 / 1010 / 0001 / 1100). Indicați un circuit elementar.

Ce se cere: Un drum închis, pe arce existente, în care vârfurile nu se repetă (în afară de primul = ultimul).

Noțiuni: matrice de adiacență în graf orientat · circuit elementar

Rezolvare pas cu pas

1. Din matrice, arcele sunt: 1→2, 1→3, 2→1, 2→3, 3→4, 4→1, 4→2.
2. a) 1,2,1,3,4,1 repetă vârful 1 la mijloc — nu e elementar.
3. b) 1,2,3,4 nu se întoarce în 1 — nu e circuit.
4. c) 1→3, 3→4, 4→2, 2→1 — toate arcele există și vârfurile sunt distincte.
5. d) folosește arcul 1→4, care nu există (a[1][4] = 0).

Răspuns final: c — 1, 3, 4, 2, 1

Verificare: Am testat fiecare variantă pe matrice: doar c are toate arcele și vârfurile distincte.

Subiectul I, 5 (4 p)

Cerința, pe scurt: Graf neorientat cu 12 noduri și 16 muchii (date în enunț). Numărul minim de muchii de eliminat ca să rămână 3 componente conexe a câte 4 noduri.

Ce se cere: Să împarți nodurile în trei grupe conexe de câte 4, tăind cât mai puține muchii între grupe.

Noțiuni: componentă conexă · graf parțial · muchie critică (punte)

Rezolvare pas cu pas

1. Muchiile care rămân sunt doar cele din interiorul grupelor; vrem să păstrăm cât mai multe dintre cele 16, adică să tăiem cât mai puține muchii dintre grupe.
2. Partea din dreapta are forma triunghi 7–8–9, muchia 9–10, triunghi 10–11–12. Grupa {9,10,11,12} este conexă (9–10, 10–11, 10–12, 11–12).
3. Rămân nodurile 1…8: grupele {1,2,3,4} (1–2, 1–3, 2–3, 2–4) și {5,6,7,8} (5–6, 6–7, 7–8) sunt amândouă conexe.
4. Muchii tăiate: 3–5, 4–5, 4–6 între primele două grupe și 7–9, 8–9 spre a treia: 5 muchii.
5. Nicio altă împărțire în trei grupe conexe de câte 4 noduri nu taie mai puțin de 5 muchii — am verificat toate împărțirile posibile (vezi verificarea).

Răspuns final: c — 5 muchii

Verificare: Forță brută în C++ peste toate cele 3¹² colorări ale nodurilor: păstrăm doar împărțirile în 3 grupe de câte 4, fiecare conexă, și numărăm muchiile dintre grupe. Minimul obținut este 5.

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

Cerința, pe scurt: Pseudocodul împarte repetat n la d (d = 2, 3, …, cât timp d·d ≤ n) și numără divizorii d care l-au împărțit; la final, dacă n ≠ 1 mai adaugă 1. Ce se afișează pentru n = 2600?

Ce se cere: Să rulezi algoritmul de mână și să recunoști ce numără.

Noțiuni: descompunere în factori primi · variabilă-indicator (p = 0/1)

Rezolvare pas cu pas

1. Algoritmul numără factorii primi distincți ai lui n: p devine 1 o singură dată pentru fiecare d care divide n, oricâte împărțiri ar face.
2. d=2: 2600 → 1300 → 650 → 325, p=1, nr=1.
3. d=3, d=4: nu divid 325, p=0.
4. d=5: 325 → 65 → 13, p=1, nr=2.
5. d=6: 6·6 = 36 > 13, ieșim din buclă. n = 13 ≠ 1, deci nr = 3.

Răspuns final: Se afișează 3 (2600 = 2³ · 5² · 13).

Verificare: Programul C++ de la punctul c, rulat cu intrarea 2600, afișează 3.

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

Cerința, pe scurt: Scrieți două numere din [10,99] pentru care se afișează 1.

Ce se cere: Numere cu un singur factor prim distinct.

Noțiuni: puteri ale unui număr prim

Rezolvare pas cu pas

1. Se afișează 1 exact când n are un singur factor prim, adică n = xᵏ cu x prim și k ≥ 1.
2. Exemple: 16 = 2⁴ și 27 = 3³ (merg și numere prime, de exemplu 11 sau 97).

Răspuns final: De exemplu 16 și 27.

Verificare: Am rulat algoritmul pentru toate numerele 10..99: cele care dau 1 sunt exact numerele prime și puterile de prime (11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, …, 81, 83, 89, 97).

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, două bucle while, decizie finală, afișare.

Noțiuni: while · operatorii / și % pe int

Rezolvare pas cu pas

1. Declarăm n, nr, d, p ca int și inițializăm nr = 0, d = 2.
2. [n/d] devine n / d (împărțire întreagă), cât timp devine while.

#include <iostream>
using namespace std;
int main()
{
    int n, nr = 0, d = 2, p;
    cin >> n;
    while (d * d <= n)
    {
        p = 0;
        while (n % d == 0)
        {
            p = 1;
            n = n / d;
        }
        nr = nr + p;
        d = d + 1;
    }
    if (n != 1)
        nr = nr + 1;
    cout << nr;
    return 0;
}

Complexitate: O(√n) pași pentru bucla exterioară.

Răspuns final: Programul de mai sus.

Verificare: Compilat fără avertismente (g++ -Wall) și rulat: 2600 → 3.

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

Cerința, pe scurt: Scrieți în pseudocod un algoritm echivalent, înlocuind a doua structură cât timp...execută cu o structură repetitivă cu test final.

Ce se cere: O buclă repetă...până când care să nu se execute deloc atunci când d nu divide n.

Noțiuni: structură cu test final · echivalența buclelor

Rezolvare pas cu pas

1. Bucla cu test final se execută cel puțin o dată, deci o protejăm cu un dacă n%d=0 atunci.
2. Condiția de oprire a lui repetă … până când este negația condiției de continuare: până când n%d≠0.

citește n (număr natural nenul)
nr ← 0; d ← 2
┌cât timp d*d ≤ n execută
│ p ← 0
│ ┌dacă n%d = 0 atunci
│ │ ┌repetă
│ │ │ p ← 1; n ← [n/d]
│ │ └până când n%d ≠ 0
│ └■
│ nr ← nr+p; d ← d+1
└■
┌dacă n ≠ 1 atunci
│ nr ← nr+1
└■
scrie nr

Răspuns final: Algoritmul echivalent de mai sus.

Verificare: Varianta cu do-while din C++ a dat aceeași ieșire ca programul original pentru toate n = 10..99 și pentru 1, 2, 97, 10⁶ și 999999937.

Subiectul al II-lea, 2 (6 p)

Cerința, pe scurt: s = "anatoliana", t = "ana". Ce afișează: strlen(s); DA/NU dacă strstr(s,t)==s; DA/NU dacă strcmp(strstr(s+1,t),t)==0?

Ce se cere: Să știi ce întorc strlen, strstr și strcmp.

Noțiuni: strlen · strstr întoarce adresa primei apariții sau NULL · strcmp întoarce 0 la egalitate

Rezolvare pas cu pas

1. strlen("anatoliana") = 10.
2. strstr(s,t) găsește "ana" chiar la începutul lui s, deci întoarce adresa s → DA.
3. s+1 = "natoliana"; prima apariție a lui "ana" este la finalul cuvântului; de acolo șirul este exact "ana", deci strcmp(…,"ana") = 0 → DA.

Răspuns final: Se afișează 10 DA DA.

Verificare: Secvența a fost rulată în C++ și a afișat „10 DA DA”.

Subiectul al II-lea, 3 (6 p)

Cerința, pe scurt: Definiți structura cu eticheta observator și variabila s astfel încât s.numar, s.stea[0].magnitudine și s.stea[0].distanta să aibă sens (cel mult 200 de stele).

Ce se cere: O structură care conține un întreg și un tablou de structuri.

Noțiuni: struct · tablou de structuri · tipuri: int pentru distanțe până la 10⁶, float pentru magnitudine

Rezolvare pas cu pas

1. numar este natural din [10,200] → int.
2. Fiecare stea are magnitudine (real) și distanță (natural ≤ 10⁶) → o structură internă; păstrăm 200 de elemente.

struct observator
{
    int numar;
    struct
    {
        float magnitudine;
        int distanta;
    } stea[200];
} s;

Răspuns final: Definiția de mai sus.

Verificare: Definiția a fost compilată și folosită exact cu expresiile din enunț.

Subiectul al III-lea, 1 (10 p)

Cerința, pe scurt: Subprogramul moda(n, pc): n ∈ [0, 10⁹] are cifrele modelelor (impar = rochie, par = costum, există cel puțin un costum); pc = numărul de ordine, de la stânga, al primului costum. Exemplu: 576798 și 5700 → pc = 3.

Ce se cere: Poziția, numărată de la stânga, a primei cifre pare.

Noțiuni: parcurgerea cifrelor cu %10 și /10 · transmitere prin referință

Rezolvare pas cu pas

1. Cifrele se extrag de la dreapta la stânga. Dacă reținem poziția ultimei cifre pare întâlnite, obținem prima cifră pară de la stânga.
2. Numărăm cifrele (k) în aceeași parcurgere; poziția de la stânga este k − poz + 1.
3. Folosim do…while ca să tratăm și n = 0, care are o cifră (0, costum) → pc = 1.
4. Pentru 5700: de la dreapta, 0 (poz=1), 0 (poz=2), 7, 5 → k = 4, pc = 4 − 2 + 1 = 3.

void moda(int n, int &pc)
{
    int poz = 0, k = 0;          // k = poziția cifrei curente, numărată de la dreapta
    do
    {
        k++;
        if (n % 10 % 2 == 0)     // cifră pară = costum
            poz = k;             // ultimul găsit de la dreapta = primul de la stânga
        n = n / 10;
    } while (n != 0);
    pc = k - poz + 1;            // k = numărul de cifre
}

Complexitate: O(numărul de cifre) ≤ 10 pași, memorie O(1).

Răspuns final: Subprogramul de mai sus.

Verificare: Rulat pe 576798 → 3, 5700 → 3, 0 → 1, 8 → 1, 1000000000 → 2, 135792 → 6.

Subiectul al III-lea, 2 (10 p)

Cerința, pe scurt: Matrice m×n (2 ≤ m,n ≤ 50, valori ≤ 10²). Pentru fiecare coloană, minimul se interschimbă cu primul element al coloanei dacă e par, altfel cu ultimul. Se afișează matricea.

Ce se cere: Pe fiecare coloană: poziția unui minim, paritatea lui, o interschimbare.

Noțiuni: parcurgere pe coloane · minim și poziția lui · interschimbare cu variabilă auxiliară

Rezolvare pas cu pas

1. Pentru coloana j căutăm linia imin a unui minim (primul găsit).
2. Dacă minimul e par, ținta este linia 0; altfel linia m−1.
3. Interschimbăm a[imin][j] cu a[țintă][j] (dacă sunt aceeași poziție, nu se schimbă nimic).
4. Pe exemplul din enunț, coloana 1 (7,1,2,5): minimul 1 e impar → se schimbă cu 5 → 7,5,2,1, exact ca în tabloul rezultat.

#include <iostream>
using namespace std;
int main()
{
    int m, n, a[50][50], i, j, imin, aux;
    cin >> m >> n;
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
            cin >> a[i][j];
    for (j = 0; j < n; j++)
    {
        imin = 0;
        for (i = 1; i < m; i++)
            if (a[i][j] < a[imin][j])
                imin = i;
        if (a[imin][j] % 2 == 0)
            i = 0;           // minim par: schimbăm cu primul element al coloanei
        else
            i = m - 1;       // minim impar: schimbăm cu ultimul element al coloanei
        aux = a[imin][j]; a[imin][j] = a[i][j]; a[i][j] = aux;
    }
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

Complexitate: O(m·n) timp, memorie doar pentru tablou.

Răspuns final: Programul de mai sus.

Verificare: Rulat pe exemplul din enunț: rezultatul coincide linie cu linie cu tabloul din enunț. Rulat și pe o matrice cu toate valorile egale (rămâne neschimbată).

Subiectul al III-lea, 3 (10 p)

Cerința, pe scurt: Șirul 0, 3, 9, 21, 45, … are termenul următor = precedentul + 2·|diferența ultimilor doi|. Se citesc ultimul și penultimul termen (≤ 10⁹); în bac.txt se scriu toți termenii, descrescător. Algoritm eficient în timp și memorie.

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

Noțiuni: relații de recurență · parcurgere înapoi a unui șir · eficiență: fără tablouri

Rezolvare pas cu pas

1. Șirul este crescător, deci |diferența| = y − z, unde x = ultimul, y = penultimul, z = antepenultimul: x = y + 2(y − z).
2. De aici z = (3y − x) / 2. Știind doi termeni consecutivi îl aflăm pe cel dinainte — mergem înapoi.
3. a) Scriem x și y; cât timp y ≠ 0, calculăm z = (3y − x)/2, îl scriem, apoi x ← y, y ← z. Ne oprim după ce am scris 0, primul termen. Folosim doar trei variabile (memorie O(1)), iar diferențele se dublează la fiecare pas, deci numărul de pași e logaritmic în valoarea citită: cel mult ~30 de pași pentru 10⁹.
4. 3y poate depăși 2³¹ − 1 când y ≈ 10⁹, de aceea folosim long long.

#include <fstream>
#include <iostream>
using namespace std;
int main()
{
    long long x, y, z;           // x = ultima lună, y = penultima lună
    cin >> x >> y;
    ofstream fout("bac.txt");
    fout << x << ' ' << y;
    while (y != 0)
    {
        // din x = y + 2*(y - z)  =>  z = (3*y - x) / 2
        z = (3 * y - x) / 2;
        fout << ' ' << z;
        x = y;
        y = z;
    }
    fout.close();
    return 0;
}

Complexitate: Timp O(log x), memorie O(1).

Răspuns final: Programul de mai sus (pentru 189 93 scrie: 189 93 45 21 9 3 0).

Verificare: Rulat pe exemplul din enunț (189 93), pe cazul cu doar două luni (3 0) și pe cel mai mare termen al șirului care nu depășește 10⁹; conținutul lui bac.txt a coincis cu șirul generat independent în Python.