Bac informatică 2023 Varianta 5, rezolvată

Lucrarea „2023 Varianta 5” de la Bacalaureatul la informatică, specializarea Mate-Info, limbajul C/C++: 3 subiecte, 90 de puncte și 3 ore de lucru la examen. Sub fiecare exercițiu ai răspunsul și explicația, închise până le deschizi, ca să încerci întâi singur.

Rezolv-o cu timpul de la examen3 ore

I II III

Enunțurile sunt cele oficiale, publicate de Ministerul Educației pe subiecte.edu.ro. Răspunsurile și explicațiile sunt scrise de subac.

Subiectul I20 de puncte

Exercițiul 14p
Indicați expresia C/C++ care are cea mai mare valoare, comparativ cu celelalte trei expresii.
- a)20*23/(2*2)
- b)20/2*23/2
- c)(20*23)/2
- d)(20*23)/2*2
Arată răspunsul și explicațiaAscunde răspunsul
Răspuns corect: d) (20*23)/2*2
* și / au aceeași prioritate și se aplică de la stânga la dreapta, iar împărțirea între numere întregi dă câtul.
a) 20·23 = 460, împărțit la 4 dă 115; b) 20/2 = 10, 10·23 = 230, 230/2 = 115; c) 460/2 = 230; d) 460/2 = 230, iar înmulțit cu 2 dă 460 — cea mai mare valoare.
Exercițiul 24p
Subprogramul f este definit alăturat.
Indicați ce se afișează în urma apelului de mai jos.
f(23);
```
void f (int n)
{ if(n!=0) f(n/2);
  cout<<n%2; | printf("%d",n%2);
}
```
- a)100111
- b)111010
- c)010111
- d)01251123
Arată răspunsul și explicațiaAscunde răspunsul
Răspuns corect: c) 010111
f(n) se autoapelează întâi cu n/2 și abia după aceea afișează n%2, deci resturile apar de la ultimul apel spre primul.
Apelurile sunt pentru 23, 11, 5, 2, 1 și 0. Se afișează, în ordine inversă, 0%2, 1%2, 2%2, 5%2, 11%2 și 23%2, adică 010111 — scrierea lui 23 în baza 2, cu un 0 în față.
Exercițiul 34p
Variabila k este de tip întreg, iar variabila s permite memorarea unui șir de maximum 50 de caractere.
Indicați valoarea variabilei k în urma executării secvenței alăturate.
```
strcpy(s,"bac2023");
s[s[2]-'a']='\0';
k=strlen(s);
```
- a)7
- b)6
- c)2
- d)1
Arată răspunsul și explicațiaAscunde răspunsul
Răspuns corect: c) 2
s[2] este caracterul 'c', iar 'c'-'a' are valoarea 2. Instrucțiunea pune terminatorul de șir pe poziția 2, deci șirul devine ba, iar strlen(s) este 2.
Exercițiul 44p
Indicați un vector de „tați” corespunzător unui arbore cu 7 noduri, în care cel puțin unul dintre noduri are trei ascendenți.
- a)0,1,2,1,1,1,2
- b)3,0,2,1,3,2,1
- c)4,3,0,3,4,4,3
- d)5,4,3,0,2,3,4
Arată răspunsul și explicațiaAscunde răspunsul
Răspuns corect: b) 3,0,2,1,3,2,1
Ascendenții unui nod sunt tatăl lui, tatăl tatălui și așa mai departe până la rădăcină: trei ascendenți înseamnă un nod pe nivelul 3.
În b) rădăcina este 2 (valoarea 0 este pe poziția 2): 3 are tatăl 2, 1 are tatăl 3, iar 4 are tatăl 1, deci 4 are ascendenții 1, 3 și 2. În a) și c) cel mai adânc nod are doar doi ascendenți, iar d) nu este un vector de tați valid, pentru că nodul 3 ar fi propriul lui tată.
Exercițiul 54p
O companie de colectare a fructelor are 6 depozite, numerotate de la 1 la 6: depozitele 1, 3 și 5 conțin mere, depozitele 2 și 4 conțin pere, iar depozitul 6 conține piersici. Compania a construit 4 benzi de transport unidirecțional: de la depozitul 1 la depozitul 5, de la depozitul 5 la depozitul 2, de la depozitul 5 la depozitul 4 și de la depozitul 6 la depozitul 1.
Dacă depozitele reprezintă vârfurile unui graf orientat, iar benzile de transport reprezintă arcele acestuia, indicați numărul minim de benzi de transport care pot fi adăugate, astfel încât graful obținut să aibă trei componente tare conexe, fiecare dintre acestea având vârfuri care corespund depozitelor cu același tip de fructe.
- a)4
- b)3
- c)2
- d)1
Arată răspunsul și explicațiaAscunde răspunsul
Răspuns corect: a) 4
Componentele trebuie să fie exact {1, 3, 5} (mere), {2, 4} (pere) și {6} (piersici).
Între 1, 3 și 5 există doar arcul 1→5, iar depozitul 3 nu are niciun arc: e nevoie de cel puțin un arc care intră în 3 și de unul care iese, de exemplu 5→3 și 3→1, care închid circuitul 1→5→3→1. Între 2 și 4 nu există niciun arc, deci trebuie 2→4 și 4→2. În total 4 arce; arcele dintre grupuri merg într-un singur sens, deci componentele nu se unesc.

Subiectul al II-lea40 de puncte

Exercițiul 1.a6p

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 valoarea afișată dacă se citește numărul 6907512.

citește x (număr natural)
 p←1; m← -1
┌cât timp p≤x execută
│ c←[x/p]%10
│┌dacă c>m atunci
││ m←c; p←p*10
││altfel
││ x←[x/(p*10)]*p+x%p
│└■
└■
┌dacă m≥0 atunci scrie x
│ altfel scrie "nul"
└■

Arată răspunsul și explicația

Răspunsul din barem: 9752

9752

Cifrele se parcurg de la dreapta, iar p este puterea lui 10 a poziției curente. O cifră se păstrează dacă e mai mare decât toate cele păstrate înaintea ei (m este cea mai mare dintre ele); altfel se elimină din număr, iar p rămâne pe loc, pentru că în locul ei vine cifra din stânga. Rămân cifrele în ordine strict descrescătoare de la stânga la dreapta.
Pentru 6907512, de la dreapta: 2 rămâne, 1 se elimină, 5 și 7 rămân, 0 se elimină, 9 rămâne, 6 se elimină: 9752.

Exercițiul 1.b6p

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 două valori distincte din intervalul [100,999] care pot fi citite astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, să se afișeze o valoare identică cu cea citită.

citește x (număr natural)
 p←1; m← -1
┌cât timp p≤x execută
│ c←[x/p]%10
│┌dacă c>m atunci
││ m←c; p←p*10
││altfel
││ x←[x/(p*10)]*p+x%p
│└■
└■
┌dacă m≥0 atunci scrie x
│ altfel scrie "nul"
└■

Arată răspunsul și explicația

Exemplu: 321 987

Numărul rămâne neschimbat exact când nicio cifră nu se elimină, adică atunci când cifrele lui sunt strict descrescătoare de la stânga la dreapta: de exemplu 321, 987, 520 sau 210.

Exercițiul 1.c10p

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 programul C/C++ corespunzător algoritmului dat.

citește x (număr natural)
 p←1; m← -1
┌cât timp p≤x execută
│ c←[x/p]%10
│┌dacă c>m atunci
││ m←c; p←p*10
││altfel
││ x←[x/(p*10)]*p+x%p
│└■
└■
┌dacă m≥0 atunci scrie x
│ altfel scrie "nul"
└■

Arată răspunsul și explicația

#include <iostream>
using namespace std;

int main()
{
    int x, p = 1, m = -1, c;
    cin >> x;
    while (p <= x)
    {
        c = x / p % 10;
        if (c > m)
        {
            m = c;
            p = p * 10;
        }
        else x = x / (p * 10) * p + x % p;
    }
    if (m >= 0) cout << x;
    else cout << "nul";
    return 0;
}

cât timp devine while, iar dacă…altfel devine if…else. [x/p]%10 se scrie x / p % 10: împărțirea întreagă și restul au aceeași prioritate și se aplică de la stânga la dreapta.

Exercițiul 1.d6p

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 în pseudocod un algoritm, echivalent cu cel dat, înlocuind structura cât timp...execută cu o structură repetitivă cu test final.

citește x (număr natural)
 p←1; m← -1
┌cât timp p≤x execută
│ c←[x/p]%10
│┌dacă c>m atunci
││ m←c; p←p*10
││altfel
││ x←[x/(p*10)]*p+x%p
│└■
└■
┌dacă m≥0 atunci scrie x
│ altfel scrie "nul"
└■

Arată răspunsul și explicația

citește x (număr natural)
p←1; m←-1
┌dacă p≤x atunci
│┌repetă
││ c←[x/p]%10
││┌dacă c>m atunci
│││ m←c; p←p*10
│││altfel
│││ x←[x/(p*10)]*p+x%p
││└■
│└până când p>x
└■
┌dacă m≥0 atunci scrie x
│ altfel scrie "nul"
└■

repetă…până când execută corpul cel puțin o dată, iar cât timp poate să nu îl execute deloc: pentru x=0 condiția p≤x este falsă de la început și se afișează nul. De aceea structura cu test final este pusă sub condiția p≤x. Condiția de oprire este negata celei de continuare: p>x.

Exercițiul 26p
Utilizând metoda backtracking, se generează toate amestecurile de apă provenită din surse distincte din mulțimea {lac, mare, ocean, ploaie, râu}, astfel încât o sursă să fie de apă sărată și una sau două surse să fie de apă dulce. Marea și oceanul sunt surse de apă sărată, iar lacul, ploaia și râul sunt surse de apă dulce. Două amestecuri sunt distincte dacă diferă prin cel puțin o sursă a apei. Primele patru soluții obținute sunt, în această ordine: (lac, mare), (lac, mare, ploaie), (lac, mare, râu) și (lac, ocean).
Scrieți soluția generată imediat înainte și soluția generată imediat după (ocean, ploaie).
Arată răspunsul și explicațiaAscunde răspunsul
Răspunsul din barem: (mare, râu) (ocean, ploaie, râu)
```
(mare, râu) (ocean, ploaie, râu)

Amestecurile se construiesc adăugând surse în ordinea din mulțime, iar un amestec se scrie de îndată ce are o sursă sărată și una sau două dulci; apoi se încearcă și prelungirea lui.
Înainte de (ocean, ploaie) vine ultimul amestec care începe cu mare: (mare, râu), după care nu mai urmează nicio sursă. După (ocean, ploaie) se încearcă prelungirea lui cu următoarea sursă, râul: (ocean, ploaie, râu).
```
Exercițiul 36p
Variabila f memorează, pentru fiecare dintre cele 10 soiuri de lalele care se vând într-o florărie, caracteristicile acestora: denumirea (șir de maximum 20 de caractere) și stocul, exprimat prin numărul de fire și prețul unui fir, în lei (numere naturale).
Știind că expresiile de mai jos au ca valori denumirea primului soi de lalele, respectiv suma, în lei, necesară pentru a cumpăra toate lalelele din acest soi, scrieți în limbajul C/C++ definiția unei structuri cu eticheta lalea, care să permită memorarea informațiilor menționate pentru un soi de lalea, și declarați corespunzător variabila f.
```
f[0].denumire     f[0].stoc.nrFire*f[0].stoc.pretFir
```
Arată răspunsul și explicațiaAscunde răspunsul
```
struct lalea
{   char denumire[21];
    struct
    {   int nrFire, pretFir;
    } stoc;
} f[10];

f[0].denumire arată că f este un tablou (cu 10 elemente, câte unul pentru fiecare soi), iar denumirea este un șir de cel mult 20 de caractere, deci un tablou de 21, cu loc pentru terminator. f[0].stoc.nrFire și f[0].stoc.pretFir arată că stoc este la rândul lui o structură, cu cele două numere naturale.
```

Subiectul al III-lea30 de puncte

Exercițiul 110p

Un număr natural nenul, n, se numește număr abundent dacă S(n)/n>S(k)/k, pentru orice număr natural nenul k (k≤n-1), unde s-a notat cu S(i) suma divizorilor pozitivi ai numărului natural nenul i. Subprogramul abundent are un singur parametru, n, prin care primește un număr natural (n∈[2,10⁶]). Subprogramul returnează valoarea 1, dacă n este un număr abundent, sau valoarea 0, în caz contrar.

Scrieți definiția completă a subprogramului.

Exemplu: pentru n=6, subprogramul returnează valoarea 1 (S(6)/6=2, iar cel mai mare raport obținut pentru valori strict mai mici decât 6 este S(4)/4=1.75), iar pentru n=7 sau n=8, subprogramul returnează valoarea 0 (S(7)/7=1.14, S(8)/8=1.87).

Arată răspunsul și explicația

int abundent(int n)
{
    int k, d;
    long long sn = 0, sk;
    for (d = 1; d * d <= n; d++)
        if (n % d == 0)
        {
            sn = sn + d;
            if (d != n / d) sn = sn + n / d;
        }
    for (k = 1; k < n; k++)
    {
        sk = 0;
        for (d = 1; d * d <= k; d++)
            if (k % d == 0)
            {
                sk = sk + d;
                if (d != k / d) sk = sk + k / d;
            }
        if (sn * k <= sk * n) return 0;
    }
    return 1;
}

Suma divizorilor unui număr se calculează luând divizorii în perechi, d și n/d, cu d până la radicalul numărului. Rapoartele S(n)/n și S(k)/k se compară fără împărțire, prin înmulțire în cruce: S(n)/n > S(k)/k este același lucru cu S(n)·k > S(k)·n, iar așa nu apar erori de rotunjire. Produsele trec de limita tipului int, de aceea se folosește long long.
Dacă pentru vreun k mai mic raportul nu este strict mai mic, n nu este abundent.

Exercițiul 210p
Pentru a identifica punctele în care se concentrează apa în albia unui râu în cazul secetei, se determină talvegul acesteia – linia care unește punctele cele mai adânci ale albiei. În acest scop s-au stabilit ns secțiuni transversale pe cursul apei, numerotate începând de la 1, și în cadrul fiecărei secțiuni s-a măsurat adâncimea apei în np puncte, numerotate începând de la 1. Din fiecare secțiune, în ordine, se include în talveg cel mai adânc punct al acesteia, iar dacă în secțiune sunt mai multe puncte aflate la aceeași adâncime, maximă, se va lua în considerare doar primul dintre ele, ca în exemplu.
Scrieți un program C/C++ care citește de la tastatură două numere naturale, ns și np (ns∈[1,10³], np∈[1,50]), și cele ns∙np elemente ale unui tablou bidimensional, valori naturale din intervalul [0,10²]. Fiecare linie a tabloului corespunde câte unei secțiuni, în ordinea numerotării acestora, iar valorile memorate pe linie reprezintă adâncimile celor np puncte stabilite pentru acea secțiune, în ordinea numerotării lor. Programul afișează pe ecran, pentru fiecare secțiune, o pereche formată din numărul de ordine al secțiunii și numărul de ordine al punctului său care s-a inclus în talveg. Numerele din fiecare pereche sunt afișate separate prin câte un caracter : (două puncte), iar fiecare pereche este urmată de un spațiu.
Exemplu: pentru ns=6, np=4 și tabloul alăturat, se afișează pe ecran valorile:
```
1:3 2:2 3:2 4:2 5:4 6:3
```
Arată răspunsul și explicațiaAscunde răspunsul
```
#include <iostream>
using namespace std;

int main()
{
    int ns, np, a[1000][50], i, j, pmax;
    cin >> ns >> np;
    for (i = 0; i < ns; i++)
        for (j = 0; j < np; j++)
            cin >> a[i][j];
    for (i = 0; i < ns; i++)
    {
        pmax = 0;
        for (j = 1; j < np; j++)
            if (a[i][j] > a[i][pmax]) pmax = j;
        cout << i + 1 << ':' << pmax + 1 << ' ';
    }
    return 0;
}

Pentru fiecare secțiune (linie) se caută poziția celei mai mari adâncimi. Comparația este strictă (>), deci la adâncimi egale rămâne prima poziție găsită, cum cere enunțul. Liniile și coloanele sunt numerotate de la 0 în tablou, de aceea la afișare se adaugă 1.
```
Exercițiul 3.a2p
Un număr natural x este numit prefix al unui număr natural y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la dreapta sa, și este numit sufix al lui y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la stânga sa.
Exemplu: 15 este prefix pentru 154 sau 1521, este sufix pentru 3415 sau 5115, dar nu este nici prefix, nici sufix pentru 15.
Fișierul bac.txt conține maximum 10⁶ numere naturale din intervalul [10,10⁴), separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul valorilor de două cifre care apar de același număr de ori ca sufix, respectiv ca prefix al numerelor din șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul de mai jos, se afișează pe ecran: 4 (pentru valorile 10, 11, 16, 34).
```
342 1684 2134 5434 111 98 98 3405 3412 7016 8634 1010 102 310
```
Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
Arată răspunsul și explicațiaAscunde răspunsul
```
Un număr de două cifre poate fi prefix sau sufix doar pentru numere cu trei sau patru cifre. Pentru un astfel de număr x, sufixul de două cifre este x%100, iar prefixul de două cifre este x/10 (la trei cifre) sau x/100 (la patru cifre). Numerele de două cifre din fișier nu au prefix sau sufix de două cifre.

Se folosesc doi vectori de frecvență, pf și sf, cu câte 100 de elemente: pe măsura citirii, pentru fiecare număr x cu cel puțin trei cifre crește pf[prefixul lui x] și sf[sufixul lui x] (un sufix mai mic decât 10, ca 05, nu are două cifre și nu se numără la final). După citire se numără valorile v de la 10 la 99 pentru care sf[v] = pf[v] și sf[v] ≠ 0.

Eficiență: fiecare număr se prelucrează o singură dată, în timp constant, iar vectorii au dimensiune fixă, deci timpul este liniar în numărul de valori din fișier.
```
Exercițiul 3.b8p
Un număr natural x este numit prefix al unui număr natural y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la dreapta sa, și este numit sufix al lui y dacă se obține din acesta prin eliminarea a cel puțin unei cifre de la stânga sa.
Exemplu: 15 este prefix pentru 154 sau 1521, este sufix pentru 3415 sau 5115, dar nu este nici prefix, nici sufix pentru 15.
Fișierul bac.txt conține maximum 10⁶ numere naturale din intervalul [10,10⁴), separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul valorilor de două cifre care apar de același număr de ori ca sufix, respectiv ca prefix al numerelor din șirul aflat în fișier. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul are conținutul de mai jos, se afișează pe ecran: 4 (pentru valorile 10, 11, 16, 34).
```
342 1684 2134 5434 111 98 98 3405 3412 7016 8634 1010 102 310
```
Scrieți programul C/C++ corespunzător algoritmului proiectat.
Arată răspunsul și explicațiaAscunde răspunsul
```
#include <fstream>
#include <iostream>
using namespace std;

int main()
{
    ifstream fin("bac.txt");
    int pf[100] = {0}, sf[100] = {0}, x, v, nr = 0;
    while (fin >> x)
        if (x > 99)
        {
            sf[x % 100]++;
            if (x > 999) pf[x / 100]++;
            else pf[x / 10]++;
        }
    fin.close();
    for (v = 10; v <= 99; v++)
        if (sf[v] == pf[v] && sf[v] != 0) nr++;
    cout << nr;
    return 0;
}

Programul face pașii de la 3.a. Pentru un număr cu trei cifre, x/10 îi taie ultima cifră, iar pentru unul cu patru cifre, x/100 îi taie ultimele două, deci în ambele cazuri rămân primele două cifre.
```

Vrei să vezi cât ai lua?

În test ai cronometrul de la examen, codul tău se compilează pe loc, iar la final primești nota.

Rezolv-o cu timpul de la examen

Bac informatică 2023 Varianta 5, rezolvată

Subiectul I20 de puncte

Exercițiul 14p

Exercițiul 24p

Exercițiul 34p

Exercițiul 44p

Exercițiul 54p

Subiectul al II-lea40 de puncte

Exercițiul 1.a6p

Exercițiul 1.b6p

Exercițiul 1.c10p

Exercițiul 1.d6p

Exercițiul 26p

Exercițiul 36p

Subiectul al III-lea30 de puncte

Exercițiul 110p

Exercițiul 210p

Exercițiul 3.a2p

Exercițiul 3.b8p