Bac informatică 2020 Varianta 5, rezolvată

Varianta 5 de la Bacalaureatul la Informatică (Mate-Info, C/C++): conține 3 subiecte (90 de puncte) și are un timp de lucru de 3 ore. Sub fiecare exercițiu găsești răspunsul corect și rezolvarea.

Începe testul3 ore

I II III

Subiecte oficiale publicate de Ministerul Educației. Rezolvări realizate de subac. Actualizat la 16 octombrie 2026.

Subiectul oficial (PDF)Baremul oficial (PDF)

📌 Despre Varianta 5 din 2020

Varianta 5 din 2020 acoperă operatorul %, recursivitatea, backtracking-ul, arborii și grafurile euleriene, structurile, matricele, șirurile de caractere și fișierele. Este o variantă potrivită pentru exersat lucrul cu cifrele unui număr și cu divizorii.

Subiectul I (20p): 5 grile: valoarea maximă a expresiei x%2020, un subprogram recursiv care afișează * de trei ori, o problemă de backtracking cu băuturi din 3 sau 4 fructe, un „frate” al unui nod într-un arbore dat prin vectorul de „tați” și numărul minim de muchii ale unui graf eulerian cu 5 noduri.

Subiectul al II-lea (40p): Un algoritm în pseudocod care scade dublul cifrelor mai mici decât 5 și adună cifrele de la 5 în sus, o structură procesor pentru cele 20 de tipuri de procesoare dintr-un depozit și o secvență care ordonează crescător doar elementele pare de pe coloana a 3-a a unei matrice.

Subiectul al III-lea (30p): Un subprogram cu divizori (kpn, care returnează al k-lea „p-număr” dintr-un interval), o problemă cu șiruri de caractere în care cuvintele cu număr impar de litere sunt înlocuite cu cuvântul în oglindă și o problemă de eficiență cu numerele de două cifre dintr-un șir citit din fișierul bac.txt.

⚠️ La ce să fii atent

La I.2: Fii atent la condiția strictă x>5! La f(17), lanțul de apeluri este 17, 9, 5 și se oprește la 5, deci * se afișează de trei ori.
La I.3: Soluțiile au 3 sau 4 fructe, deci după fiecare soluție de trei fructe vin prelungirile ei la patru. Așa se ajunge ca a șasea soluție să fie (căpșune, mere, portocale).
La I.5: Un graf eulerian are toate gradele pare. Nodul de grad 4 e legat de toți ceilalți, deci fiecare dintre ei are gradul cel puțin 2. Suma gradelor e cel puțin 12, deci graful are cel puțin 6 muchii.
La III.2: Cuvintele în oglindă trebuie să fie distincte. Un cuvânt cu număr impar de litere care se citește la fel din ambele capete, ca reper sau o, nu se înlocuiește.
La III.3: Intervalul (a,b) este deschis, deci capetele nu fac parte din el. Reține cel mai mic și cel mai mare număr de două cifre, apoi afișează minimul minus 1 și maximul plus 1. În exemplu, din 10 și 40 se obține 9 41.

Subiectul I

20 de puncte

Exercițiul 1 4p Expresii și operatori
Variabila x este de tip întreg și poate memora un număr natural din intervalul [0,10^{^9}).
Indicați valoarea maximă pe care o poate avea expresia C/C++ alăturată.
```
x%2020
```
- a)20.2
- b)2019
- c)2020
- d)495049
Vezi rezolvareaAscunde rezolvarea
Răspuns corect: b) 2019
Restul împărțirii la 2020 nu poate fi niciodată mai mare sau egal cu 2020 — cel mult 2019, adică varianta b), obținut de exemplu pentru x=2019.
Varianta a) nu poate fi: % între întregi dă tot un întreg, nu 20,2. Variantele c) și d) sunt prea mari: un rest la împărțirea cu 2020 stă mereu între 0 și 2019.
Exercițiul 2 4p Recursivitate
Subprogramul f este definit alăturat.
Indicați apelul în urma căruia simbolul * se afișează de trei ori.
```
void f(int x)
{
 cout<<"*";  |  printf("*");
 if(x>5) f((x+1)/2);
}
```
- a)f(30);
- b)f(21);
- c)f(17);
- d)f(8);
Vezi rezolvareaAscunde rezolvarea
Răspuns corect: c) f(17);
Subprogramul afișează * înainte de a verifica dacă mai coboară, deci fiecare apel scrie exact un asterisc. Trebuie deci numărate apelurile:
apel lanțul de apeluri asteriscuri
a) f(30) 30 → 15 → 8 → 4 4
b) f(21) 21 → 11 → 6 → 3 4
c) f(17) 17 → 9 → 5 3
d) f(8) 8 → 4 2
Coborârea se oprește când x nu mai e strict mai mare decât 5. La f(17): (17+1)/2=9, apoi (9+1)/2=5, iar 5 nu e mai mare decât 5 — deci f(5) afișează al treilea asterisc și se oprește. Răspunsul e c).
Exercițiul 3 4p Backtracking
Utilizând metoda backtracking se generează toate modalitățile de a prepara o băutură din câte 3 sau 4 tipuri de fructe distincte din mulțimea {căpșune, mere, pepene, pere, portocale}. Primele patru soluții generate sunt, în această ordine:
1. (căpșune, mere, pepene)
2. (căpșune, mere, pepene, pere)
3. (căpșune, mere, pepene, portocale)
4. (căpșune, mere, pere)
Indicați cea de a șasea soluție generată.
- a)(pepene, pere, portocale)
- b)(mere, pepene, pere, portocale)
- c)(căpșune, mere, portocale)
- d)(căpșune, mere, pere, pepene)
Vezi rezolvareaAscunde rezolvarea
Răspuns corect: c) (căpșune, mere, portocale)
Fructele se iau în ordinea din mulțime: 1 căpșune, 2 mere, 3 pepene, 4 pere, 5 portocale. Backtracking-ul construiește șiruri crescătoare de indici și raportează o soluție de fiecare dată când lungimea e 3 sau 4 — de aceea o soluție de trei fructe e urmată de prelungirile ei la patru:
nr. soluție
1 1,2,3 — căpșune, mere, pepene
2 1,2,3,4 — …, pere
3 1,2,3,5 — …, portocale
4 1,2,4 — căpșune, mere, pere
5 1,2,4,5 — …, portocale
6 1,2,5 — căpșune, mere, portocale
Primele patru coincid cu cele din enunț. A șasea este c).
Varianta d) n-ar putea apărea niciodată în această ordine: (căpșune, mere, pere, pepene) are indicii 1,2,4,3, iar backtracking-ul nu generează indici descrescători.
Exercițiul 4 4p Arbori
Un arbore cu 9 noduri, numerotate de la 1 la 9, este reprezentat prin vectorul de „tați” (8,6,4,2,3,0,4,2,7).
Indicați un „frate” al nodului 4.
- a)1
- b)2
- c)7
- d)8
Vezi rezolvareaAscunde rezolvarea
Răspuns corect: d) 8
În vectorul de „tați”, poziția i spune cine e tatăl nodului i:
nod 1 2 3 4 5 6 7 8 9
tată 8 6 4 2 3 0 4 2 7
Tatăl nodului 4 este 2. „Frații” lui sunt celelalte noduri care au tot tatăl 2 — cauți în tabel valoarea 2: o mai găsești doar la nodul 8.
Deci răspunsul e d). Nodurile 3 și 7 sunt *fiii* lui 4, nu frații lui, iar 6 e rădăcina, fiindcă are tatăl 0.
Exercițiul 5 4p Grafuri neorientate
Un graf neorientat eulerian cu 5 noduri are un nod cu gradul 4.
Indicați numărul minim de muchii ale grafului.
- a)4
- b)6
- c)8
- d)10
Vezi rezolvareaAscunde rezolvarea
Răspuns corect: b) 6
Un graf eulerian este conex și are toate gradele pare.
Nodul de grad 4 e legat de toate celelalte patru noduri, deci fiecare dintre ele are deja gradul cel puțin 1. Dar gradele trebuie să fie pare, deci fiecare dintre cele patru are gradul cel puțin 2.
Suma gradelor este atunci cel puțin 4 + 2+2+2+2 = 12, iar numărul de muchii e jumătate din suma gradelor: cel puțin 6 — varianta b).
Se și atinge: nodul central legat cu toate celelalte patru, plus două muchii care leagă restul două câte două. Toate gradele sunt pare, graful e conex, deci e eulerian, cu exact 6 muchii.

apel	lanțul de apeluri	asteriscuri
a) `f(30)`	30 → 15 → 8 → 4	4
b) `f(21)`	21 → 11 → 6 → 3	4
c) `f(17)`	17 → 9 → 5	3
d) `f(8)`	8 → 4	2

nr.	soluție
1	1,2,3 — căpșune, mere, pepene
2	1,2,3,4 — …, pere
3	1,2,3,5 — …, portocale
4	1,2,4 — căpșune, mere, pere
5	1,2,4,5 — …, portocale
6	1,2,5 — căpșune, mere, portocale

nod	1	2	3	4	5	6	7	8	9
tată	8	6	4	2	3	0	4	2	7

Subiectul al II-lea

40 de puncte

Exercițiul 1.a 6p Algoritmi în pseudocod
Algoritmul alăturat este reprezentat în pseudocod.
S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.
Scrieți ce se afișează dacă se citește numărul 247388.
```
citește n (număr natural)
 m←0
┌repetă
│ c←n%10; n←[n/10]
│┌dacă c<5 atunci m←m-2*c
││altfel m←m+c
│└■
└până când n=0
┌dacă m=0 atunci scrie 'DA'
│altfel scrie m, 'NU'
└■
```
Vezi rezolvareaAscunde rezolvarea
Răspunsul din barem: 5 NU
5NU
Algoritmul ia cifrele lui 247388 de la dreapta la stânga. Cifrele mici (sub 5) se scad de două ori, cele de la 5 în sus se adună:
cifra ce face m
8 +8 8
8 +8 16
3 −6 10
7 +7 17
4 −8 9
2 −4 5
Cum m=5 nu e zero, se execută ramura altfel, care scrie întâi valoarea lui m și apoi textul: 5NU, fără spațiu între ele.
Exercițiul 1.b 6p Algoritmi în pseudocod
Același algoritm ca la 1.a.
S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.
Scrieți două numere din intervalul [10^{^2},10^{^3}), cu cifre distincte, care pot fi citite astfel încât, pentru fiecare dintre acestea, în urma executării algoritmului, să se afișeze DA.
Vezi rezolvareaAscunde rezolvarea
840 și 630
Se afișează DA doar când suma iese exact 0. Fiecare cifră sub 5 aduce −2c, iar fiecare cifră de la 5 în sus aduce +c, deci trebuie ca cifrele mari să compenseze exact dublul celor mici.
- 840: cifra 0 aduce 0, cifra 4 aduce −8, cifra 8 aduce +8. Total: 0.
- 630: 0 aduce 0, 3 aduce −6, 6 aduce +6. Total: 0.
Amândouă au trei cifre distincte și sunt în intervalul cerut.
Orice altă pereche construită la fel merge: e de ajuns ca o cifră mare să fie dublul uneia mici, iar a treia să fie 0 — de pildă 420 sau 860.

cifra	ce face	m
8	+8	8
8	+8	16
3	−6	10
7	+7	17
4	−8	9
2	−4	5

Exercițiul 1.c 10p Algoritmi în pseudocod

Același algoritm ca la 1.a.

S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.

Scrieți programul C/C++ corespunzător algoritmului dat.

Vezi rezolvarea

#include <iostream>
using namespace std;

int main()
{
    int n, m = 0, c;
    cin >> n;
    do
    {
        c = n % 10;
        n = n / 10;
        if (c < 5)
            m = m - 2 * c;
        else
            m = m + c;
    } while (n != 0);
    if (m == 0)
        cout << "DA";
    else
        cout << m << "NU";
    return 0;
}

Exercițiul 1.d 6p Algoritmi în pseudocod
Același algoritm ca la 1.a.
S-a notat cu a%b restul împărțirii numărului natural a la numărul natural nenul b și cu [c] partea întreagă a numărului real c.
Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind adecvat structura repetă...până când cu o structură repetitivă cu test inițial.
Vezi rezolvareaAscunde rezolvarea
``citește n (număr natural) m←0 c←n%10; n←[n/10] ┌dacă c<5 atunci m←m-2*c │altfel m←m+c └■ ┌cât timp n≠0 execută │ c←n%10; n←[n/10] │┌dacă c<5 atunci m←m-2*c ││altfel m←m+c │└■ └■ ┌dacă m=0 atunci scrie 'DA' │altfel scrie m, 'NU' └■``
repetă execută corpul cel puțin o dată, iar o structură cu test inițial poate să nu-l execute deloc. De aceea prima prelucrare se scoate afară, înaintea buclei, iar cât timp n≠0 se ocupă de restul cifrelor.
Fără această primă prelucrare scoasă în față, algoritmul n-ar mai fi echivalent: pentru n=0 cel dat afișează DA, fiindcă tot intră o dată în corp, pe când un simplu cât timp n≠0 n-ar intra niciodată și ar lăsa m neatins — tot DA, dar din întâmplare, nu pentru că a prelucrat cifra 0.
Exercițiul 2 6p Tipul înregistrare (struct)
Variabila p memorează simultan, pentru fiecare dintre cele 20 de tipuri de procesoare dintr-un depozit, următoarele date: producătorul (o literă mare a alfabetului englez), frecvența procesorului (număr natural) și prețul produsului (număr real).
Știind că expresiile C/C++ de mai jos au ca valori producătorul primului procesor, respectiv frecvența și prețul acestuia, scrieți definiția unei structuri cu eticheta procesor, care permite memorarea datelor despre un procesor, și declarați corespunzător variabila p.
```
p[0].producator   p[0].frecventa   p[0].pret
```
Vezi rezolvareaAscunde rezolvarea
```cpp struct procesor { char producator; int frecventa; double pret; };
procesor p[20]; ```
Tipurile vin din enunț, nu din expresii: producătorul e o literă, deci char; frecvența e număr natural, deci int; prețul e număr real, deci double (merge și float).
Numele câmpurilor sunt impuse de expresiile date — producator, frecventa, pret — iar p e un tablou de 20 de structuri, câte una pentru fiecare tip de procesor din depozit.
Exercițiul 3 6p Tablouri bidimensionale
Variabilele i, j și k sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 6 linii și 4 coloane, numerotate începând de la 0, cu elemente numere naturale din intervalul [0,50].
Scrieți o secvență de instrucțiuni în urma executării căreia să se rearanjeze elementele pare situate pe coloana a 3-a a tabloului, astfel încât acestea să fie ordonate crescător, de sus în jos, în cadrul aceleiași coloane, iar celelalte elemente ale tabloului să își păstreze pozițiile, ca în exemplu.
Exemplu: pentru tabloul
Vezi rezolvareaAscunde rezolvarea
``cpp for (i = 0; i < 6; i++) for (j = i + 1; j < 6; j++) if (a[i][2] % 2 == 0 && a[j][2] % 2 == 0 && a[i][2] > a[j][2]) { k = a[i][2]; a[i][2] = a[j][2]; a[j][2] = k; }``
Coloana a 3-a are indicele 2, fiindcă numerotarea începe de la 0.
Ideea e să sortezi doar elementele pare, lăsând impare pe loc: compari perechi de poziții i<j de pe coloană, dar intri în if numai dacă amândouă valorile sunt pare. Așa, valorile impare nu participă niciodată la vreun schimb și rămân exact unde erau, iar cele pare ajung ordonate crescător între pozițiile pe care le ocupau ele.
Pe exemplu, coloana 4 8 5 2 1 0 are pare pe pozițiile 0, 1, 3 și 5; ordonate, ele devin 0 2 4 8 și se așază pe aceleași poziții, deci coloana ajunge 0 2 5 4 1 8.

Subiectul al III-lea

30 de puncte

Exercițiul 1 10p Subprograme
Un număr natural nenul se numește p-număr dacă are aceeași paritate cu suma divizorilor săi pozitivi.
Exemplu: 10 și 25 sunt p-numere (10 are aceeași paritate cu 18=1+2+5+10, iar 25 are aceeași paritate cu 31=1+5+25).
Subprogramul kpn, are trei parametri, a, b și k, prin care primește câte un număr natural din intervalul [1,10^{^6}] (a≤b). Subprogramul returnează cel de al k-lea p-număr din intervalul [a,b] sau -1, dacă nu există cel puțin k astfel de numere în acest interval.
Scrieți definiția completă a subprogramului.
Exemplu: dacă a=27, b=50 și k=3, atunci subprogramul returnează 34.
Vezi rezolvareaAscunde rezolvarea
```
int kpn(int a, int b, int k)
{
    int cate = 0;
    for (int x = a; x <= b; x++)
    {
        int s = 0;
        for (int d = 1; d * d <= x; d++)
            if (x % d == 0)
            {
                s = s + d;
                if (d != x / d)
                    s = s + x / d;
            }
        if (s % 2 == x % 2)
        {
            cate++;
            if (cate == k)
                return x;
        }
    }
    return -1;
}
```
Exercițiul 2 10p Șiruri de caractere
Două cuvinte distincte se numesc în oglindă dacă fiecare dintre ele se obține prin citirea literelor celuilalt de la dreapta la stânga.
Exemplu: animate și etamina sunt în oglindă, iar pentru cuvântul reper nu există un cuvânt cu care să fie în oglindă.
Se consideră un text cu cel mult 100 de caractere, în care cuvintele sunt formate din litere mici ale alfabetului englez și sunt separate prin câte un spațiu.
Scrieți un program C/C++ care citește de la tastatură un text de tipul menționat mai sus și îl transformă în memorie, înlocuind fiecare cuvânt cu număr impar de litere cu acel cuvânt cu care el este în oglindă, dacă acesta există, ca în exemplu. Programul afișează pe ecran textul obținut sau mesajul nu exista, dacă în text nu s-a înlocuit niciun cuvânt.
Exemplu: pentru textul era o selectie reper de desene animate prezenta se obține textul are o selectie reper de desene etamina prezenta iar pentru textul un reper pentru desene se afișează pe ecran mesajul nu exista
Vezi rezolvareaAscunde rezolvarea
```
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[101], cuv[51][101];
    cin.getline(s, 101);
    int k = 0;
    for (char *p = strtok(s, " "); p != NULL; p = strtok(NULL, " "))
    {
        strcpy(cuv[k], p);
        k++;
    }
    int schimbate = 0;
    for (int i = 0; i < k; i++)
    {
        int n = strlen(cuv[i]);
        if (n % 2 == 1)
        {
            char oglinda[101];
            for (int j = 0; j < n; j++)
                oglinda[j] = cuv[i][n - 1 - j];
            oglinda[n] = '\0';
            if (strcmp(oglinda, cuv[i]) != 0)
            {
                strcpy(cuv[i], oglinda);
                schimbate++;
            }
        }
    }
    if (schimbate == 0)
    {
        cout << "nu exista";
        return 0;
    }
    for (int i = 0; i < k; i++)
    {
        cout << cuv[i];
        if (i < k - 1)
            cout << ' ';
    }
    return 0;
}
```
Exercițiul 3.a 2p Algoritmi eficienți
Fișierul bac.txt conține un șir de cel mult 10^{^6} numere naturale din intervalul [0,10^{^9}], separate prin câte un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două numere naturale a și b (a<b), astfel încât oricare termen al șirului care are exact două cifre să aparțină intervalului (a,b), iar valoarea expresiei b-a să fie minimă. Dacă șirul nu are niciun termen de două cifre, pe ecran se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține valorile 7 2 40 5 11 15 10 122 18 350 se afișează pe ecran numerele 9 41.
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Vezi rezolvareaAscunde rezolvarea
Timp de executare: O(n) · Memorie: O(1)
Se citește șirul o singură dată, din fișier, fără să fie păstrat.
Din toate numerele mă interesează doar cele de exact două cifre, adică cele din intervalul [10,99]. Dintre ele țin minte doar două valori: cel mai mic și cel mai mare văzut până acum.
La final, intervalul (a,b) trebuie să le cuprindă pe toate și să fie cât mai scurt. Cum intervalul e deschis — capetele nu fac parte din el — cea mai strânsă alegere este a = minim-1 și b = maxim+1. Dacă n-am întâlnit niciun termen de două cifre, afișez nu exista.
Pe exemplul din enunț, termenii de două cifre sunt 40, 11, 15, 10 și 18: minimul e 10, maximul 40, deci se afișează 9 41.
De ce e eficient: fiecare număr e citit și comparat o singură dată, deci timpul e O(n). Memoria e O(1): se rețin două valori, indiferent că șirul poate avea 10⁶ numere — nu e nevoie să fie păstrat nici măcar un singur termen mai mult.
Exercițiul 3.b 8p Algoritmi eficienți
Fișierul bac.txt conține un șir de cel mult 10^{^6} numere naturale din intervalul [0,10^{^9}], separate prin câte un spațiu.
Se cere să se afișeze pe ecran, separate printr-un spațiu, două numere naturale a și b (a<b), astfel încât oricare termen al șirului care are exact două cifre să aparțină intervalului (a,b), iar valoarea expresiei b-a să fie minimă. Dacă șirul nu are niciun termen de două cifre, pe ecran se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă fișierul conține valorile 7 2 40 5 11 15 10 122 18 350 se afișează pe ecran numerele 9 41.
Scrieți programul C/C++ corespunzător algoritmului proiectat.
Vezi rezolvareaAscunde rezolvarea
```
#include <fstream>
#include <iostream>
using namespace std;

int main()
{
    ifstream f("bac.txt");
    long long x, minim = -1, maxim = -1;
    while (f >> x)
        if (x >= 10 && x <= 99)
        {
            if (minim < 0 || x < minim)
                minim = x;
            if (maxim < 0 || x > maxim)
                maxim = x;
        }
    f.close();
    if (minim < 0)
        cout << "nu exista";
    else
        cout << minim - 1 << " " << maxim + 1;
    return 0;
}
```

Vrei să vezi ce notă ai lua la examen?

Intră în modul simulare: ai cronometru de 3 ore, codul ți se compilează pe loc, iar la final primești nota conform baremului.

Începe simularea3 ore

Bac informatică 2020 Varianta 5, rezolvată

📌 Despre Varianta 5 din 2020

⚠️ La ce să fii atent

Subiectul I

Exercițiul 1 4p Expresii și operatori

Exercițiul 2 4p Recursivitate

Exercițiul 3 4p Backtracking

Exercițiul 4 4p Arbori

Exercițiul 5 4p Grafuri neorientate

Subiectul al II-lea

Exercițiul 1.a 6p Algoritmi în pseudocod

Exercițiul 1.b 6p Algoritmi în pseudocod

Exercițiul 1.c 10p Algoritmi în pseudocod

Exercițiul 1.d 6p Algoritmi în pseudocod

Exercițiul 2 6p Tipul înregistrare (struct)

Exercițiul 3 6p Tablouri bidimensionale

Subiectul al III-lea

Exercițiul 1 10p Subprograme

Exercițiul 2 10p Șiruri de caractere

Exercițiul 3.a 2p Algoritmi eficienți

Exercițiul 3.b 8p Algoritmi eficienți