BAC Informatică C/C++ - iunie 2023 (Varianta 5)

Operatorii * și / au aceeași prioritate și se aplică de la stânga la dreapta (împărțire întreagă).

• a. 20*23/(2*2) $= 460/4 = 115$
• b. 20/2*23/2 $= 10 \cdot 23 / 2 = 230/2 = 115$
• c. (20*23)/2 $= 460/2 = 230$
• d. (20*23)/2*2 $= 230 \cdot 2 = 460$

Cea mai mare valoare este $460$, deci răspunsul corect este d.

Item grilă: se cerea expresia C/C++ cu cea mai mare valoare dintre a. 2023/(22), b. 20/223/2, c. (2023)/2, d. (2023)/22. Barem: 4 puncte pentru litera d. Justificare: operatorii și / au aceeași prioritate și se evaluează de la stânga la dreapta, deci a = 460/4 = 115, b = 1023/2 = 115, c = 460/2 = 230, d = 460/22 = 2302 = 460 (cea mai mare). Fără punctaj parțial.

Apelurile recursive se fac înaintea afișării, deci afișarea are loc la revenirea din recursivitate:

$f(23) \to f(11) \to f(5) \to f(2) \to f(1) \to f(0)$

La revenire se afișează, în ordine: $0\%2=0$, $1\%2=1$, $2\%2=0$, $5\%2=1$, $11\%2=1$, $23\%2=1$.

Pe ecran apare 010111, adică reprezentarea binară a lui $23$ ($10111$) precedată de un $0$. Răspunsul corect este c.

Item grilă: subprogram recursiv void f(int n) { if(n!=0) f(n/2); cout<<n%2; } apelat cu f(23); se cerea ce se afișează. Barem: 4 puncte pentru litera c (se afișează 010111). Justificare: apelurile recursive coboară f(23)->f(11)->f(5)->f(2)->f(1)->f(0), iar afișările se fac la revenire, în ordinea 0%2=0, 1%2=1, 2%2=0, 5%2=1, 11%2=1, 23%2=1, adică 010111 (reprezentarea binară a lui 23 precedată de 0). Fără punctaj parțial.

După strcpy, șirul este "bac2023". Caracterul s[2] este 'c', iar 'c'-'a' $= 2$.

Atribuirea s[2]='\0' trunchiază șirul la primele două caractere: "ba".

Astfel k=strlen(s) $= 2$. Răspunsul corect este c.

Item grilă: după strcpy(s,"bac2023"); s[s[2]-'a']='\0'; k=strlen(s); se cerea valoarea lui k. Barem: 4 puncte pentru litera c (k=2). Justificare: s[2]='c', 'c'-'a'=2, deci s[2] primește '\0' și șirul devine "ba", cu lungimea 2. Fără punctaj parțial.

La varianta b, vectorul de tați (3,0,2,1,3,2,1) descrie arborele cu rădăcina în nodul $2$ (singurul cu tatăl $0$):

• tatăl nodului $1$ este $3$, tatăl nodului $3$ este $2$;
• tatăl nodului $4$ este $1$.

Lanțul de ascendenți ai nodului $4$ este: $1$, apoi $3$, apoi $2$ (rădăcina), deci nodul $4$ are exact trei ascendenți.

La varianta a, adâncimea maximă este 2 (niciun nod cu trei strămoși), iar variantele c și d nu oferă un nod cu trei ascendenți în structura de arbore cerută. Răspunsul corect este b.

Item grilă: se cerea vectorul de tați al unui arbore cu 7 noduri în care cel puțin un nod are trei ascendenți (strămoși), dintre 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. Barem: 4 puncte pentru litera b. Justificare: la varianta b rădăcina este nodul 2 (tată 0), iar nodul 4 are tatăl 1, care are tatăl 3, care are tatăl 2, deci nodul 4 are trei ascendenți (1, 3, 2). Celelalte variante fie nu au un nod cu trei ascendenți, fie nu descriu un arbore valid. Fără punctaj parțial.

Componentele tare conexe cerute sunt $\{1,3,5\}$ (mere), $\{2,4\}$ (pere) și $\{6\}$ (piersici).

• Pentru $\{1,3,5\}$: există doar arcul $1 \to 5$. Un circuit care trece prin cele trei vârfuri necesită minimum 3 arce, deci trebuie adăugate încă 2 (de exemplu $5 \to 3$ și $3 \to 1$).
• Pentru $\{2,4\}$: nu există niciun arc între ele, deci sunt necesare 2 arce ($2 \to 4$ și $4 \to 2$).
• $\{6\}$: un vârf singur formează o componentă tare conexă, nu necesită arce.

Arcele existente $5 \to 2$, $5 \to 4$, $6 \to 1$ leagă componente diferite și nu strică proprietatea. Total minim: $2+2=4$ arce. Răspunsul corect este a.

Item grilă: graf orientat cu 6 vârfuri și arcele 1->5, 5->2, 5->4, 6->1; se cerea numărul minim de arce de adăugat pentru trei componente tare conexe formate din depozitele cu același tip de fructe: {1,3,5} (mere), {2,4} (pere), {6} (piersici). Barem: 4 puncte pentru litera a (4 arce). Justificare: pentru {1,3,5} există doar arcul 1->5, deci sunt necesare încă 2 arce (de exemplu 5->3 și 3->1) pentru un circuit; pentru {2,4} nu există niciun arc între ele, deci sunt necesare 2 arce (2->4 și 4->2); {6} este tare conexă ca vârf izolat în componentă. Total minim: 2+2=4. Fără punctaj parțial.

Algoritmul parcurge cifrele de la unități spre stânga; p indică poziția curentă, iar m reține cea mai mare cifră întâlnită. Dacă cifra curentă c este strict mai mare decât m, este păstrată; altfel este eliminată din număr.

Trasare pentru $x = 6907512$:

• $c=2 > -1$: se păstrează, $m=2$, $p=10$
• $c=1 \le 2$: se elimină, $x=690752$
• $c=5 > 2$: se păstrează, $m=5$, $p=100$
• $c=7 > 5$: se păstrează, $m=7$, $p=1000$
• $c=0 \le 7$: se elimină, $x=69752$
• $c=9 > 7$: se păstrează, $m=9$, $p=10000$
• $c=6 \le 9$: se elimină, $x=9752$
• $p=10000 > 9752$: bucla se oprește

Cum $m=9 \ge 0$, se afișează 9752.

Pseudocod: citește x; p=1, m=-1; cât timp p<=x: c=[x/p]%10; dacă c>m atunci m=c, p=p10, altfel x=[x/(p10)]*p+x%p; la final, dacă m>=0 scrie x, altfel scrie "nul". Se cerea valoarea afișată pentru x=6907512. Barem: 6 puncte pentru răspunsul corect 9752. Algoritmul elimină, de la dreapta spre stânga, fiecare cifră care nu este strict mai mare decât toate cifrele din dreapta ei; din 6907512 rămân cifrele 9, 7, 5, 2. Fără punctaj parțial precizat în barem.

Numărul rămâne neschimbat doar dacă nicio cifră nu este eliminată, adică fiecare cifră este strict mai mare decât toate cifrele din dreapta ei. Asta înseamnă că cifrele numărului sunt în ordine strict descrescătoare de la stânga la dreapta.

Exemple de răspunsuri corecte: $321$ și $964$ (sau $875$, $210$, $953$ etc.).

Verificare pentru $321$: $c=1$ se păstrează ($m=1$), $c=2>1$ se păstrează ($m=2$), $c=3>2$ se păstrează ($m=3$); nimic nu se elimină, se afișează $321$.

Pentru pseudocodul care elimină din x fiecare cifră ce nu este strict mai mare decât toate cifrele aflate în dreapta ei, se cereau două valori distincte din [100,999] pentru care valoarea afișată este identică cu cea citită. Barem: 6 puncte, câte 3 puncte pentru fiecare dintre cele două numere conform cerinței. Corect este ORICARE număr de trei cifre cu cifrele în ordine strict descrescătoare (de exemplu 321, 964, 875, 210). Un număr fără această proprietate nu primește punctele respective.

#include <iostream>
using namespace std;

int main() {
    long long x, p, m, c;
    cin >> x;
    p = 1;
    m = -1;
    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;
}

Împărțirea întreagă din C/C++ realizează direct [x/p], iar cele două structuri de decizie și bucla while urmează fidel pseudocodul.

Se cerea programul C/C++ corespunzător pseudocodului: citește x; p=1, m=-1; cât timp p<=x: c=[x/p]%10; dacă c>m atunci m=c, p=p10, altfel x=[x/(p10)]*p+x%p; la final, dacă m>=0 se afișează x, altfel se afișează textul nul. Barem (10 puncte): variabile declarate conform cerinței 1p; date citite conform cerinței 1p; date afișate conform cerinței 1p; instrucțiune repetitivă conform cerinței 2p; instrucțiuni de decizie conform cerinței 3p (se acordă numai 2p dacă doar una dintre instrucțiunile de decizie este corectă); atribuiri conform cerinței 1p; corectitudine globală a programului (structură, sintaxă) 1p. Împărțirile [x/p] se realizează ca împărțiri întregi.

Structura cu test final execută corpul cel puțin o dată, deci trebuie protejată pentru cazul $x=0$ (când bucla inițială nu se execută deloc):

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"
└■

Testul final până când p>x este negația condiției p≤x, iar decizia exterioară asigură echivalența și pentru $x=0$ (se afișează "nul", ca în algoritmul dat).

Se cerea rescrierea în pseudocod a algoritmului dat, înlocuind structura cât timp...execută cu o structură repetitivă cu test final (repetă...până când). Barem (6 puncte): structură repetitivă de tipul cerut 2p (se acordă chiar dacă algoritmul obținut nu este echivalent; orice formă de structură cu test final este acceptată: repetă...până când, repeat...until etc.); aspecte specifice ale secvenței obținute prin înlocuire 3p (se acordă numai 2p dacă doar unul dintre aspecte este corect: expresia logică pentru testul final, respectiv păstrarea echivalenței pentru cazul x=0, când corpul buclei inițiale nu se execută deloc, de exemplu protejând bucla cu o decizie dacă p≤x); algoritm complet, corectitudine globală 1p.

Soluțiile sunt generate în ordinea lexicografică a submulțimilor cu elemente în ordinea lac, mare, ocean, ploaie, râu, păstrând doar amestecurile valide (o sursă sărată + una sau două surse dulci):

(lac,mare), (lac,mare,ploaie), (lac,mare,râu), (lac,ocean), (lac,ocean,ploaie), (lac,ocean,râu), (mare,ploaie), (mare,ploaie,râu), (mare,râu), (ocean,ploaie), (ocean,ploaie,râu), (ocean,râu)

Imediat înainte de (ocean,ploaie) se generează (`mare`,`râu`), iar imediat după se generează (`ocean`,`ploaie`,`râu`).

Backtracking pe submulțimile mulțimii ordonate {lac, mare, ocean, ploaie, râu}, reținând amestecurile cu exact o sursă de apă sărată (mare sau ocean) și una sau două surse de apă dulce (lac, ploaie, râu); primele patru soluții: (lac,mare), (lac,mare,ploaie), (lac,mare,râu), (lac,ocean). Se cereau soluția generată imediat înainte și cea imediat după (ocean,ploaie). Barem: 6 puncte, câte 3 puncte pentru fiecare soluție: imediat înainte este (mare,râu), imediat după este (ocean,ploaie,râu). Ordinea completă a soluțiilor: (lac,mare), (lac,mare,ploaie), (lac,mare,râu), (lac,ocean), (lac,ocean,ploaie), (lac,ocean,râu), (mare,ploaie), (mare,ploaie,râu), (mare,râu), (ocean,ploaie), (ocean,ploaie,râu), (ocean,râu).

struct lalea {
    char denumire[21];
    struct {
        int nrFire;
        int pretFir;
    } stoc;
};

struct lalea f[10];

Câmpul denumire are 21 de caractere (20 utile plus terminatorul '\0'), câmpul stoc este o structură imbricată cu nrFire și pretFir, iar f este un tablou cu 10 elemente de tip lalea, câte unul pentru fiecare soi.

Se cerea definiția unei structuri C/C++ cu eticheta lalea (denumire: șir de maximum 20 de caractere; stoc: structură imbricată cu câmpurile nrFire și pretFir, numere naturale) și declararea variabilei f ca tablou de 10 elemente de acest tip, compatibilă cu expresiile f[0].denumire și f[0].stoc.nrFire*f[0].stoc.pretFir. Barem (6 puncte): structură/înregistrare definită conform cerinței 4p (câte 1p pentru: definire principial corectă a unei structuri, câmpuri de pe primul nivel, câmpuri de pe al doilea nivel, etichetă/nume conform cerinței); variabilă declarată conform cerinței (tablou cu 10 elemente de tip lalea) 1p; corectitudine globală a secvenței 1p.

Calculăm suma divizorilor cu un subprogram auxiliar, apoi comparăm raportul lui n cu maximul rapoartelor pentru $k < n$, folosind împărțire reală:

int sumaDiv(int x) {
    int s = 0;
    for (int d = 1; d <= x; d++)
        if (x % d == 0)
            s = s + d;
    return s;
}

int abundent(int n) {
    double rmax = 0, r;
    for (int k = 1; k < n; k++) {
        r = 1.0 * sumaDiv(k) / k;
        if (r > rmax)
            rmax = r;
    }
    if (1.0 * sumaDiv(n) / n > rmax)
        return 1;
    return 0;
}

Înmulțirea cu 1.0 forțează împărțirea reală (altfel raportul s-ar trunchia la întreg). Pentru $n=6$: $S(6)/6 = 12/6 = 2$, iar maximul pentru $k<6$ este $S(4)/4 = 7/4 = 1.75$, deci se returnează 1. Suma divizorilor se poate calcula și mai eficient, parcurgând doar divizorii $d$ cu $d \cdot d \le x$ și adunând perechea $x/d$.

Se cerea definiția completă a subprogramului abundent cu un parametru n (număr natural din [2,10^6]), care returnează 1 dacă S(n)/n > S(k)/k pentru orice k natural nenul, k<=n-1 (S(i) = suma divizorilor pozitivi ai lui i), respectiv 0 în caz contrar. Exemplu: abundent(6)=1, abundent(7)=abundent(8)=0. Barem (10 puncte): antet al subprogramului conform cerinței 2p (câte 1p pentru structură și parametrul de intrare); proprietate verificată conform cerinței 6p (câte 1p pentru fiecare aspect: identificarea unui divizor al unui număr, algoritm de bază pentru calculul sumei unei serii de valori, divizorii corecți însumați, împărțire reală pentru raport, algoritm principial corect de verificare a proprietății, numerele suport verificate corect - toate valorile k de la 1 la n-1); instrucțiune de returnare a rezultatului conform cerinței 1p; variabile locale declarate, corectitudine globală a subprogramului 1p. Atenție la capcana împărțirii întregi: rapoartele S(i)/i trebuie calculate cu împărțire reală.

#include <iostream>
using namespace std;

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

Comparația strictă a[i][j] > a[i][pmax] garantează că, la adâncimi egale, rămâne selectat primul punct de adâncime maximă din secțiune. Pentru exemplul dat se afișează 1:3 2:2 3:2 4:2 5:4 6:3.

Se cerea un program C/C++ care citește ns si np (ns<=1000, np<=50) și un tablou bidimensional ns x np cu valori naturale din [0,100], apoi afișează pentru fiecare linie (secțiune) perechea: numărul liniei, caracterul :, poziția primului element maxim de pe linie, fiecare pereche urmată de un spațiu. Exemplu: pentru liniile (2 4 5 3), (2 6 6 3), (1 5 2 5), (1 3 3 3), (3 4 3 5), (0 1 2 1) se afișează 1:3 2:2 3:2 4:2 5:4 6:3. Barem (10 puncte): variabilă de tip tablou bidimensional declarată conform cerinței 1p; date citite conform cerinței 1p; valori cu proprietatea cerută determinate 6p (câte 2p pentru fiecare aspect: algoritm de bază pentru determinarea valorii maxime dintr-o serie, determinarea poziției unui maxim - prima poziție la egalitate, valori corecte pentru fiecare secțiune); date afișate în formatul cerut (număr:poziție și spațiu după fiecare pereche) 1p; variabile simple declarate, corectitudine globală a programului 1p.

Algoritm: Folosim doi vectori de frecvență cu indici de la 10 la 99: pf[v] numără de câte ori apare v ca prefix, iar sf[v] de câte ori apare ca sufix. Citim numerele din fișier unul câte unul, fără a le memora. Numerele de două cifre nu produc nici prefix, nici sufix de două cifre (ar trebui eliminată cel puțin o cifră). Pentru fiecare număr x cu $x > 99$: sufixul de două cifre este $x \% 100$ (numărat doar dacă este cel puțin 10), iar prefixul de două cifre este $[x/10]$ dacă x are trei cifre, respectiv $[x/100]$ dacă are patru cifre. La final numărăm valorile $v \in [10,99]$ cu pf[v] = sf[v] și sf[v] nenul.

Eficiență: fișierul este parcurs o singură dată, deci timpul este liniar, $O(N)$ pentru $N$ numere; memoria este constantă, două tablouri de cel mult 100 de elemente, fără a memora șirul de $10^6$ numere.

Pentru problema numărării valorilor de două cifre care apar de același număr de ori ca sufix și ca prefix al numerelor din fișierul bac.txt (maximum 10^6 numere din [10,10^4)), se cerea descrierea în limbaj natural a unui algoritm eficient și justificarea eficienței. Barem (2 puncte): descriere coerentă a algoritmului conform cerinței 1p (se acordă chiar dacă algoritmul ales nu este eficient); elemente de eficiență justificate conform cerinței 1p. Soluția eficientă așteptată: doi vectori de frecvență pf și sf (pentru prefixele, respectiv sufixele de două cifre); la citirea fiecărui număr x>99 se actualizează sf[x%100] (doar dacă x%100>=10) și pf[[x/10]] pentru x de trei cifre, respectiv pf[[x/100]] pentru x de patru cifre; la final se numără valorile v din [10,99] cu pf[v]=sf[v] și sf[v] nenul. Eficiență: o singură parcurgere a fișierului, timp liniar O(N), memorie O(1) (două tablouri de cel mult 100 de elemente), fără memorarea celor 10^6 numere.

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

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

Fiecare număr de trei cifre are exact un prefix de două cifre ($[x/10]$), iar fiecare număr de patru cifre, de asemenea ($[x/100]$); sufixul de două cifre este $x \% 100$, valid doar dacă este cel puțin 10. Algoritmul este liniar: o singură parcurgere a fișierului și doi vectori de frecvență de 100 de elemente. Pentru exemplul dat, valorile numărate sunt 10, 11, 16 și 34, deci se afișează 4.

Se cerea programul C/C++ care citește numerele din fișierul bac.txt (maximum 10^6 numere naturale din [10,10^4), separate prin spații) și afișează pe ecran numărul valorilor de două cifre care apar de același număr de ori ca sufix și ca prefix al numerelor din fișier (pentru exemplul dat: 4). Barem (8 puncte): operații cu fișiere (declarare, pregătire în vederea citirii, citire din fișier) 1p; valoarea cerută determinată corect 5p (se acordă numai 3p dacă algoritmul este principial corect dar nu oferă rezultatul cerut pentru toate seturile de date; aspecte: prefixele de două cifre sunt [x/10] pentru numere de trei cifre și [x/100] pentru patru cifre, sufixele x%100 doar dacă sunt >=10, numerele de două cifre nu contribuie, comparația finală pf[v]=sf[v] cu sf[v] nenul); eficiența algoritmului 1p (se acordă numai pentru un algoritm liniar, cu vectori de frecvență, fără memorarea întregului șir); variabile declarate, afișarea datelor, corectitudine globală 1p.