BAC Informatică C/C++ - iunie 2025 (Varianta 1)

Calculăm expresia dată: $2025 \bmod 2019 = 6$, deci 2025%2019+6 are valoarea $6 + 6 = 12$.

Evaluăm apoi variantele, ținând cont că / între întregi este împărțire întreagă, iar % este restul:

Singura expresie cu valoarea 12 este cea de la litera d.

Item grilă: expresia C/C++ cu aceeași valoare ca 2025%2019+6 (a. 2025/2020+5, b. 2025/2021+8, c. 2025%2020+5, d. 2025%2021+8). Barem: 4 puncte pentru litera d. Expresia dată valorează 6+6 = 12, iar 2025%2021+8 = 4+8 = 12. Fără punctaj parțial.

Cazul de bază este $n = 0$: bucla for nu se execută niciun pas, deci f(0) nu afișează nimic. Construim de jos în sus:

• f(1): $i = 1$ impar → f(0) (nimic), apoi 1 ⟹ afișează 1
• f(2): $i = 1$ → 1; $i = 2$ par → 2, apoi f(1) = 1 ⟹ afișează 121
• f(3): $i = 1$ → 1; $i = 2$ → 2 urmat de f(1) = 1, deci 21; $i = 3$ impar → f(2) = 121 urmat de 3, deci 1213

Concatenând: 1 + 21 + 1213 = 1211213, litera a.

Metoda de lucru: la recursie cu buclă, nu urmări apelurile în minte - calculează întâi ce afișează f(0), apoi f(1), apoi f(2), și folosește rezultatele deja obținute.

Item grilă: ce afișează apelul f(3) pentru subprogramul recursiv dat (pentru i de la 1 la n: dacă i este par se afișează i și apoi se apelează f(i-1), altfel se apelează f(i-1) și apoi se afișează i). Barem: 4 puncte pentru litera a (se afișează 1211213). Fără punctaj parțial.

Cerința are trei condiții: tabloul trebuie să fie bidimensional, să memoreze numere reale și să aibă cel mult 100 de elemente.

• a. float m[2,50]; - în C/C++ virgula dintre paranteze este operatorul virgulă, nu un separator de dimensiuni; declarația este echivalentă cu float m[50];, deci un tablou unidimensional.
• b. float m[4][25]; - bidimensional, elemente reale, $4 \cdot 25 = 100$ elemente. Corect.
• c. float m[10] x float m[10]; - nu este o sintaxă C/C++ validă.
• d. int m[100]; - unidimensional și cu elemente întregi.

Răspunsul corect este litera b.

Item grilă: declararea unui tablou bidimensional care poate memora maximum 100 de numere reale. Barem: 4 puncte pentru litera b (float m[4][25], adică 4·25 = 100 elemente reale). Fără punctaj parțial.

Codurile se generează în ordine lexicografică (crescătoare), pentru că la fiecare poziție cifrele se încearcă în ordinea crescătoare a mulțimii. Ultimul cod generat este deci cel mai mare cod posibil:

• primele trei cifre, impare distincte, cât mai mari: 9, 7, 5;
• ultimele trei cifre, pare distincte, cât mai mari: 8, 6, 4.

Ultimul cod este 975864. Penultimul se obține modificând ultima poziție, singura care se schimbă cel mai des: cu prefixul 97586 fixat, cifrele pare rămase sunt 0, 2 și 4, deci codurile cu acest prefix sunt, în ordine, 975860, 975862, 975864. Penultimul cod generat este așadar 975862, litera c.

Atenție la capcană: penultimul NU se obține micșorând prima cifră - variantele a și b schimbă a doua cifră, ceea ce ar da coduri mult mai mici, generate cu mult înainte.

Item grilă de backtracking: coduri de 6 cifre distincte, primele trei impare și ultimele trei pare, generate în ordine lexicografică; se cere penultimul cod. Barem: 4 puncte pentru litera c (975862). Ultimul cod generat este 975864, iar penultimul se obține scăzând pe ultima poziție. Fără punctaj parțial.

Într-un graf orientat fără circuite vârfurile pot fi numerotate astfel încât orice arc să meargă de la un vârf cu număr mai mic la unul cu număr mai mare (o sortare topologică). Atunci pentru fiecare pereche de vârfuri există cel mult un arc, iar numărul maxim de arce este numărul de perechi:

$$C_{10}^2 = \frac{10 \cdot 9}{2} = 45.$$

Răspunsul corect este litera b. Varianta d, $10 \cdot 9 = 90$, este numărul maxim de arce ale unui graf orientat oarecare cu 10 vârfuri - dar acolo ambele arce dintre două vârfuri ar forma un circuit de lungime 2, interzis aici.

Item grilă: numărul maxim de arce ale unui graf orientat fără circuite cu 10 vârfuri (a. 10, b. 45, c. 50, d. 90). Barem: 4 puncte pentru litera b (45). Fără punctaj parțial.

Algoritmul caută primul pătrat perfect din intervalul $[m,n]$: pentru fiecare $i$ determină cel mai mic $x$ cu $x \cdot x \ge i$ și verifică dacă $x \cdot x = i$.

Ciclul se oprește pentru că $nr \neq 0$, deci se afișează 9.

Pentru algoritmul pseudocod dat (caută, pornind de la i = m, prima valoare i ≤ n care este pătrat perfect, verificând-o prin căutarea celui mai mic x cu x*x ≥ i; scrie acea valoare sau 0 dacă nu există), se cere ce se afișează pentru m = 7 și n = 17. Barem: 6 puncte pentru răspunsul corect: 9. Fără punctaj parțial.

Algoritmul afișează primul pătrat perfect din $[m,25]$. Ca acesta să fie chiar 25, intervalul nu trebuie să conțină niciun pătrat perfect mai mic decât 25. Pătratele perfecte din apropiere sunt $16 = 4^2$ și $25 = 5^2$, deci trebuie ca $m > 16$, adică $m \in [17,25]$ (condiția $m \le n$ dă limita superioară).

Două valori posibile: m = 17 și m = 20.

Verificare pentru $m = 20$: $i$ ia pe rând valorile 20, 21, 22, 23, 24 - niciuna pătrat perfect - apoi $i = 25$, unde $x = 5$ și $x \cdot x = 25 = i$, deci se afișează 25.

Același algoritm. Se cere: două valori distincte ale lui m pentru care, cu n = 25, se afișează 25. Barem: 6 puncte pentru răspuns corect, câte 3 puncte pentru fiecare dintre cele două numere conform cerinței - oricare două numere naturale distincte din intervalul [17,25].

Traducerea este directă, cu o singură atenție: repetă ... până când C din pseudocod devine do { ... } while (!C); în C/C++, pentru că while continuă cât timp condiția este adevărată, iar până când se oprește când devine adevărată.

#include <iostream>
using namespace std;

int main()
{
    int m, n, nr, i, x;
    cin >> m >> n;
    nr = 0;
    i = m;
    do
    {
        x = 1;
        while (x*x < i)
            x = x+1;
        if (x*x == i)
            nr = i;
        else
            i = i+1;
    } while (!(i > n || nr != 0));
    cout << nr;
    return 0;
}

Condiția finală se poate scrie și direct în forma echivalentă while (i <= n && nr == 0);, obținută prin legile lui De Morgan.

Același algoritm. Se cere programul C/C++ corespunzător. Barem, total 10 puncte: declarare a variabilelor 1p; citire a datelor 1p; afișare a datelor 1p; instrucțiune de decizie 2p; instrucțiuni repetitive 3p (doar 2p dacă doar una dintre cele două structuri repetitive este conform cerinței); atribuiri 1p; corectitudine globală 1p. Structura repetă...până când se traduce prin do...while cu condiția negată.

Diferența esențială dintre cele două structuri: cât timp testează înainte și se poate executa de zero ori, pe când o structură cu test final se execută cel puțin o dată. Cum $x$ pornește de la 1, pentru $i = 1$ avem deja $x \cdot x \ge i$ și bucla originală nu face niciun pas - de aceea noua buclă trebuie protejată de o decizie:

citește m,n (numere naturale nenule, m ≤ n)
nr ← 0; i ← m
repetă
    x ← 1
    dacă x*x < i atunci
        repetă
            x ← x+1
        până când x*x ≥ i
    dacă x*x = i atunci
        nr ← i
    altfel
        i ← i+1
până când i > n sau nr ≠ 0
scrie nr

Condiția de oprire a noii bucle este negarea condiției de continuare a celei vechi: cât timp x*x < i devine până când x*x ≥ i.

Același algoritm. Se cere înlocuirea structurii cât timp...execută cu o structură repetitivă cu test final. Barem, total 6 puncte: utilizare a unei structuri repetitive cu test final 2p; aspecte specifice ale secvenței obținute 3p (câte un aspect: echivalență a algoritmului pentru cazul inițial x*x ≥ i, expresie logică pentru testul final); algoritm complet și corectitudine globală 1p. Punctul-cheie: o structură cu test final se execută cel puțin o dată, deci cazul în care bucla cât timp nu s-ar executa niciun pas trebuie protejat cu o decizie.

Un graf este eulerian dacă este conex și toate vârfurile au grad par. Cel mai simplu subgraf de acest tip este un triunghi, în care fiecare vârf are gradul 2.

Din listele de adiacență, nodurile 1, 2 și 3 sunt legate două câte două: muchiile $[1,2]$, $[1,3]$ și $[2,3]$ există toate. Alegem deci

$$V = \{1, 2, 3\}, \qquad E = \{[1,2],\, [1,3],\, [2,3]\}.$$

Verificare: subgraful este conex, fiecare dintre cele trei noduri are gradul 2 (par) și niciun nod nu este izolat, deci este eulerian - ciclul eulerian este chiar $1 \to 2 \to 3 \to 1$.

Soluția nu este unică: de exemplu $V = \{1,4,5,6\}$ cu $E = \{[1,4],[4,5],[5,6],[6,1]\}$ (un ciclu de lungime 4) este tot un răspuns corect.

Se cere un subgraf eulerian fără noduri izolate al grafului neorientat cu 6 noduri dat prin liste de adiacență. Barem: 6 puncte pentru răspuns corect, câte 2 puncte pentru fiecare aspect: mulțimea nodurilor unui subgraf fără noduri izolate, mulțimea muchiilor corespunzătoare mulțimii nodurilor alese, caracterul eulerian al grafului obținut. Orice subgraf conex cu toate gradele pare este acceptat.

Expresiile din enunț impun structura câmpurilor: p.cod și p.pret sunt câmpuri simple, iar p.informatii[0] arată că informatii este un tablou cu 3 elemente.

struct prajitura
{
    int cod;
    float pret;
    int informatii[3];
};

prajitura p;

Codul este un număr natural de două cifre și cele trei informații sunt numere naturale din $[1,10^2]$, deci tipul int este suficient pentru toate; prețul este număr real, deci float (sau double). În C, declararea variabilei se scrie struct prajitura p;.

Se cere definiția unei structuri cu eticheta prajitura (cod - număr natural de două cifre, pret - număr real, informatii - trei numere naturale) și declararea variabilei p, astfel încât expresiile p.cod, p.pret și p.informatii[0] să fie valide. Barem: 6 puncte pentru răspuns corect - 4p pentru definirea structurii (câte 1p pentru: definire de bază a unei structuri, etichetă, câmpuri de tip simplu cod și pret, câmp de tip structurat informatii), 1p pentru declararea variabilei, 1p pentru corectitudinea globală a secvenței.

Cifra de comparație este cifra unităților lui n, adică n%10; ea se calculează o singură dată. Apoi parcurgem intervalul $[x,y]$ și, pentru fiecare număr, îi verificăm toate cifrele cu ciclul standard c%10 / c/10.

int ascendent(int n, int x, int y)
{
    int u = n%10, s = 0, i, c, ok;
    for (i = x; i <= y; i++)
    {
        c = i;
        ok = 1;
        if (c == 0)
            ok = (u == 0);
        while (c > 0)
        {
            if (c%10 < u)
                ok = 0;
            c = c/10;
        }
        if (ok)
            s = s+i;
    }
    return s;
}

Două detalii care se pierd ușor:

1. numărul 0 nu intră în bucla while (c > 0), deci ar fi declarat ascendent din oficiu; el are o singură cifră, 0, deci este ascendent numai dacă cifra unităților lui n este tot 0; 2. dacă nu există niciun ascendent, suma rămâne 0, deci chiar valoarea cerută de enunț - nu este nevoie de un caz separat.

Verificare pe exemplu: pentru n=827 cifra unităților este 7, iar în $[9,800]$ numerele cu toate cifrele $\ge 7$ sunt cele din enunț, cu suma 7893.

Se cere definiția completă a unui subprogram C/C++ ascendent(n, x, y) care returnează suma numerelor din [x,y] ale căror cifre sunt toate ≥ cifra unităților lui n, sau 0 dacă nu există. Barem, total 10 puncte: antet al subprogramului 2p (câte 1p pentru structură și pentru parametrii de intrare); determinare a valorii cerute 6p (câte 1p pentru: identificarea cifrei unităților, compararea unei cifre cu o altă cifră, algoritm de bază pentru verificarea unei proprietăți, cifre suport verificate, algoritm de bază pentru determinarea sumei, numere ascendent însumate); instrucțiune de returnare 1p; declarare a variabilelor locale și corectitudine globală 1p.

Parcurgem textul cuvânt cu cuvânt, delimitând fiecare cuvânt între poziția lui de început și primul spațiu care urmează. Pentru un cuvânt de lungime pară $2k$, salvăm prima jumătate într-un tablou auxiliar, mutăm a doua jumătate în față și punem jumătatea salvată la sfârșit - transformarea se face în memorie, în același șir.

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

char t[205], aux[105];

int main()
{
    cin.getline(t, 205);
    int n = strlen(t), i = 0, j, lg, k, p, ok = 0;
    while (i < n)
    {
        j = i;
        while (j < n && t[j] != ' ')
            j++;
        lg = j-i;
        if (lg%2 == 0)
        {
            ok = 1;
            k = lg/2;
            for (p = 0; p < k; p++)
                aux[p] = t[i+p];
            for (p = 0; p < k; p++)
                t[i+p] = t[i+k+p];
            for (p = 0; p < k; p++)
                t[i+k+p] = aux[p];
        }
        i = j+1;
    }
    if (ok)
        cout << t;
    else
        cout << "nu exista";
    return 0;
}

Lungimea cuvântului nu se schimbă prin interschimbare, deci textul poate fi modificat pe loc, fără să fie nevoie de un al doilea șir pentru rezultat. Variabila ok reține dacă a existat măcar un cuvânt cu număr par de litere; dacă nu, se afișează mesajul cerut.

Se cere un program C/C++ care citește un text de cel mult 200 de caractere și înlocuiește în memorie fiecare cuvânt cu număr par de litere cu semioglinditul său (prima jumătate interschimbată cu a doua), afișând textul obținut sau mesajul nu exista dacă toate cuvintele au număr impar de litere. Barem, total 10 puncte: declarare a unei variabile care să memoreze un șir de caractere 1p; citire a datelor 1p; transformare a șirului 6p (câte 1p pentru: identificarea unui cuvânt cu număr par/impar de litere, caractere obținute în prima jumătate, caractere obținute în a doua jumătate, cuvinte înlocuite/păstrate, transformare în memorie, tratarea cazului nu exista); afișare a datelor 1p; declarare a variabilelor simple și corectitudine globală 1p. Citirea trebuie făcută cu cin.getline (textul conține spații).

Citim prima pereche $(h_1,h_2)$ - intervalul de care dispune tânărul - și apoi, pe măsură ce citim fiecare dintre perechile următoare $(c_1,c_2)$, îi calculăm intersecția cu intervalul disponibil:

$$v_1 = \max(h_1,c_1), \qquad v_2 = \min(h_2,c_2).$$

Dacă $v_2 - v_1 \ge 1$, adică intersecția conține cel puțin o oră, incrementăm contorul de muzee convenabile și reținem numărul de ordine curent ca fiind al ultimului muzeu convenabil. La final afișăm contorul și acest număr de ordine.

Eficiența: fiecare linie a fișierului este citită și prelucrată o singură dată, deci timpul de executare este liniar în numărul de muzee, $O(N)$ - minimul posibil, pentru că orice soluție trebuie măcar să citească datele. Memoria folosită este constantă, $O(1)$: nu se rețin intervalele citite într-un tablou, ci doar intervalul disponibil, contorul, numărul de ordine curent și cel al ultimului muzeu convenabil. Cum fișierul poate avea până la $10^5$ linii, evitarea tabloului este exact ceea ce se cere prin „eficient din punctul de vedere al memoriei utilizate".

Se cere descrierea în limbaj natural a algoritmului eficient proiectat pentru problema muzeelor virtuale, cu justificarea eficienței. Barem, total 2 puncte: descriere coerentă a algoritmului 1p (se acordă chiar dacă algoritmul ales nu este eficient); justificare a elementelor de eficiență 1p. Soluția eficientă este liniară și cu memorie constantă: se citește prima pereche (h1,h2), apoi fiecare pereche următoare se prelucrează pe loc, calculând intersecția [max(h1,crt1), min(h2,crt2)].

Programul citește din fișier pereche cu pereche, fără să memoreze nimic în plus:

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

int main()
{
    ifstream f("bac.in");
    int h1, h2, c1, c2, v1, v2;
    int nr = 0, ultim = 0, crt = 0;
    f >> h1 >> h2;
    while (f >> c1 >> c2)
    {
        crt++;
        v1 = (h1 > c1) ? h1 : c1;
        v2 = (h2 < c2) ? h2 : c2;
        if (v2-v1 >= 1)
        {
            nr++;
            ultim = crt;
        }
    }
    f.close();
    cout << nr << " " << ultim;
    return 0;
}

Pe exemplul din enunț, cu intervalul disponibil $[16,19]$:

Se afișează 3 4, ca în enunț.

Se cere programul C/C++ corespunzător algoritmului eficient descris la punctul a. Barem, total 8 puncte: operații cu fișiere - declarare, pregătire în vederea citirii, citire din fișier 1p; determinare a valorilor cerute 5p (numai 3p dacă algoritmul parcurge pașii necesari, dar cu detalii care conduc la o rezolvare parțială); utilizare a unui algoritm eficient 1p (se acordă numai pentru un algoritm liniar, care utilizează eficient memoria); declarare a variabilelor, afișare a datelor și corectitudine globală 1p.