BAC Informatică C/C++ - iunie 2024 (Varianta 3)

Analizăm fiecare variantă:

• x%2==0 && (y+1)%2!=0: prima condiție cere ca x să fie par; a doua cere ca y+1 să fie impar, adică y par. Expresia este 1 exact când ambele numere sunt pare.
• (x-y)%2==0 și (x+y)%2==0 sunt adevărate și când x și y sunt ambele impare (de exemplu x=3, y=5), deci nu convin.
• x%2==y%2 cere doar aceeași paritate, nu paritate pară.

Răspunsul corect este a.

Item grilă: se cerea expresia C/C++ cu valoarea 1 dacă și numai dacă variabilele întregi x și y sunt ambele pare. Barem: 4 puncte pentru litera a. (x%2==0 impune x par, iar (y+1)%2!=0 impune y+1 impar, deci y par; variantele b, c, d sunt adevărate și când x și y sunt ambele impare.) Nu se acordă punctaj parțial.

Urmărim lanțul de apeluri recursive:

1. f(2020,0): 2020 ≥ 10, deci apelează f(202,1), urmând să afișeze apoi 0 (2020%10) și 0 (y). 2. f(202,1): apelează f(20,2), apoi afișează 2 și 1. 3. f(20,2): apelează f(2,3), apoi afișează 0 și 2. 4. f(2,3): 2 < 10, afișează 2, apoi 3.

La întoarcerea din recursivitate se afișează, în ordine: 2 3 (din f(2,3)), 0 2 (din f(20,2)), 2 1 (din f(202,1)), 0 0 (din f(2020,0)).

Rezultat: 23022100, litera d.

Item grilă: se cerea ce afișează apelul recursiv f(2020,0) pentru subprogramul dat (dacă x<10 afișează x, altfel apelează f(x/10,y+1) apoi afișează x%10; la final afișează mereu y). Barem: 4 puncte pentru litera d (se afișează 23022100). Trasare: f(2,3) afișează 2 și 3; revenind, f(20,2) afișează 0 și 2; f(202,1) afișează 2 și 1; f(2020,0) afișează 0 și 0. Nu se acordă punctaj parțial.

Primele șase permutări păstrează prefixul par (2,4,6) și parcurg în ordine lexicografică toate cele 3! = 6 aranjamente ale valorilor impare (1,3,5).

După epuizarea lor, backtracking trece la următorul prefix par în ordine lexicografică: după (2,4,6) urmează (2,6,4). Prima permutare cu acest prefix folosește cea mai mică ordine a valorilor impare, adică (1,3,5).

A șaptea permutare generată este (2,6,4,1,3,5), litera c.

Item grilă: backtracking generează permutările lui {1..6} cu valorile pare pe primele trei poziții și cele impare pe ultimele trei; primele șase încep cu prefixul (2,4,6) și epuizează în ordine lexicografică aranjamentele valorilor impare. Se cerea a șaptea permutare. Barem: 4 puncte pentru litera c, adică (2,6,4,1,3,5): următorul prefix par în ordine lexicografică după (2,4,6) este (2,6,4), completat cu cea mai mică ordine a valorilor impare (1,3,5). Nu se acordă punctaj parțial.

x este un tablou cu 20 de elemente de tip struct ciocolata. Al 11-lea sortiment se află pe indicele 10 (indexarea începe de la 0), deci elementul este x[10], iar câmpul său se accesează cu operatorul punct: x[10].tip.

Celelalte variante aplică operatorii în ordine greșită (indexează câmpul sau numele tipului în loc de variabilă).

Răspunsul corect este d.

Item grilă: pentru tabloul de structuri struct ciocolata { char tip; float pret; } x[20]; se cerea expresia care accesează tipul celui de al 11-lea sortiment. Barem: 4 puncte pentru litera d (x[10].tip: al 11-lea element are indicele 10, iar câmpul se accesează cu operatorul punct pe element). Nu se acordă punctaj parțial.

Suma gradelor într-un graf neorientat este dublul numărului de muchii: $2 \cdot 10 = 20$.

Pentru a maximiza numărul de noduri, fiecare nod trebuie să consume cât mai puțin din suma gradelor:

• cele 2 noduri de grad 0 nu consumă nimic;
• cele 6 noduri cu grad impar au gradul minim 1, consumând în total 6;
• rămân $20 - 6 = 14$ pentru nodurile cu grad par nenul, deci cu gradul minim 2: cel mult $14 : 2 = 7$ noduri.

Numărul maxim de noduri este $2 + 6 + 7 = 15$, litera b.

Item grilă: graf neorientat cu 10 muchii, două noduri de grad 0, șase noduri cu grade impare, restul cu grade pare nenule; se cerea numărul maxim de noduri. Barem: 4 puncte pentru litera b (15 noduri). Justificare: suma gradelor este 2 x 10 = 20; cele șase noduri impare consumă minim 6 (câte 1), rămân 20 - 6 = 14 pentru nodurile pare nenule, deci cel mult 7 noduri de grad 2; total 2 + 6 + 7 = 15. Nu se acordă punctaj parțial.

Primul număr citit este $n = 5$, iar următoarele cinci sunt valorile lui x.

Se afișează valoarea 9.

Pentru algoritmul pseudocod dat (p pornește de la 1; pentru fiecare dintre cele n numere citite x se execută repetat x <- [x/3] până când x <= 3, iar dacă valoarea finală x este nenulă se face p <- p*x; la final se scrie p), se cerea valoarea afișată pentru citirile 5, 15, 27, 10, 1, 17 (deci n=5, apoi x: 15, 27, 10, 1, 17). Barem: 6 puncte pentru răspunsul corect: 9. Verificare: 15->5->1 (p=1), 27->9->3 (p=3), 10->3 (p=9), 1->0 (nu modifică), 17->5->1 (p=9). Nu se acordă punctaj parțial.

Bucla repetă...până când se execută cel puțin o dată, deci fiecare x citit este înlocuit repetat cu $[x/3]$ până devine cel mult 3; valoarea finală este 0, 1, 2 sau 3.

Pentru ca produsul afișat să fie 4, cele două valori finale trebuie să fie 2 și 2 (factorizările cu factori nenuli cel mult 3 sunt doar 2·2; 4·1 nu este posibilă pentru că 4 > 3).

Un număr se reduce la 2 exact când aparține unui interval de forma $[2 \cdot 3^k, 3^{k+1})$ cu $k \ge 1$: [6,9), [18,27), [54,81), [162,243), [486,729).

Un exemplu de răspuns corect: 6 și 7 (6 → 2, 7 → 2, p = 2·2 = 4). Alt exemplu: 6 și 18.

Pentru algoritmul pseudocod dat (fiecare x citit este redus repetat prin x <- [x/3] până când x <= 3, iar valorile finale nenule se înmulțesc în p), cu n=2, se cereau două numere distincte din [0,1000] pentru care se afișează 4. Fiecare număr trebuie să se reducă la valoarea finală 2 (4 = 2 x 2, singura factorizare posibilă cu factori <= 3 nenuli). Barem: 6 puncte; se acordă câte 2 puncte pentru fiecare aspect specific (număr de valori scrise, prima valoare, a doua valoare) conform cerinței. Se punctează valori naturale din reuniunea intervalelor de forma [2*3^k, 3^(k+1)), cu k natural, k in {1,2,3,4,5}, adică [6,9), [18,27), [54,81), [162,243), [486,729); de exemplu 6 și 7, sau 6 și 18.

#include <iostream>
using namespace std;

int main()
{
    int n, x, i;
    long long p = 1;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> x;
        do
        {
            x = x / 3;
        } while (x > 3);
        if (x != 0)
            p = p * x;
    }
    cout << p;
    return 0;
}

Puncte de atenție: bucla interioară este do...while pentru că structura repetă...până când se execută cel puțin o dată, iar condiția de continuare este negația condiției de oprire (x > 3). Împărțirea întreagă x/3 calculează exact partea întreagă $[x/3]$.

Se cerea programul C/C++ echivalent cu algoritmul pseudocod dat (citește n; pentru fiecare dintre cele n numere x: repetă x = x/3 până când x <= 3; dacă x != 0, p = p*x; afișează p). 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 (se acordă numai 2p dacă doar una dintre instrucțiunile repetitive este conform cerinței); atribuiri 1p; corectitudine globală a programului 1p (structură, sintaxă, alte aspecte neprecizate). Bucla interioară trebuie să fie de tip do...while (se execută cel puțin o dată), iar împărțirea x/3 pe întregi realizează partea întreagă.

citește n (număr natural nenul)
p ← 1
i ← 1
cât timp i ≤ n execută
    citește x (număr natural)
    repetă
        x ← [x/3]
    până când x ≤ 3
    dacă x ≠ 0 atunci
        p ← p*x
    i ← i+1
scrie p

Echivalența cu structura pentru se obține prin trei elemente: inițializarea contorului (i ← 1) înaintea buclei, condiția de continuare (i ≤ n) și actualizarea contorului (i ← i+1) la sfârșitul corpului buclei.

Se cerea rescrierea în pseudocod a algoritmului dat, înlocuind structura pentru i <- 1,n execută cu o structură cât timp...execută echivalentă (inițializare i <- 1 înaintea buclei, condiție i <= n, incrementare i <- i+1 în corp), păstrând restul algoritmului. Barem, total 6 puncte: utilizare a unei structuri repetitive de tipul indicat 2p (orice formă cât timp...execută / while...do); aspecte specifice ale secvenței obținute prin înlocuire 3p (câte 1p pentru inițializarea contorului, expresia de continuare, actualizarea contorului); algoritm complet și corectitudine globală 1p.

Din vectorul de tați (3,0,2,5,2,5,1,5) deducem: rădăcina este nodul 2 (tatăl 0); copiii lui 2 sunt 3 și 5; copilul lui 3 este 1; copilul lui 1 este 7; copiii lui 5 sunt 4, 6 și 8.

Lanțurile care pornesc din rădăcină:

• 2, 3, 1, 7 (4 noduri)
• 2, 5, 4 / 2, 5, 6 / 2, 5, 8 (câte 3 noduri)

Cel mai lung lanț elementar cu extremitatea inițială în rădăcină este 2, 3, 1, 7.

Pentru arborele cu 8 noduri dat prin vectorul de tați (3,0,2,5,2,5,1,5) (tatăl nodului 1 este 3, nodul 2 este rădăcina, tatăl lui 3 este 2, tatăl lui 4 este 5, tatăl lui 5 este 2, tatăl lui 6 este 5, tatăl lui 7 este 1, tatăl lui 8 este 5), se cerea cel mai lung lanț elementar cu extremitatea inițială în rădăcină, cu nodurile enumerate în ordinea parcurgerii. Barem: 6 puncte pentru răspunsul corect 2,3,1,7; se acordă câte 2 puncte pentru fiecare aspect specific (lanț cu o extremitate în rădăcină, lanț elementar, lungime maximă a lanțului) conform cerinței.

Observăm poziția valorilor 4: în colțul din stânga-sus apar exact acolo unde $i + j \le 3$ (pe linia 0 primele 4 coloane, pe linia 1 primele 3 etc.), iar în colțul din dreapta-jos exact acolo unde $i + j \ge 13$ (pe linia 5 doar coloana 8, pe linia 8 coloanele 5-8). În rest, elementele sunt 2.

Secvența completată, cu două instrucțiuni de atribuire:

for(i=0;i<9;i++)
   for(j=0;j<9;j++)
      if(i+j<=3 || i+j>=13)
         a[i][j]=4;
      else
         a[i][j]=2;

Se cerea completarea corpului dublei parcurgeri for(i=0;i<9;i++) for(j=0;j<9;j++) cu instrucțiuni (cel mult patru de atribuire) astfel încât tabloul a de 9x9 să conțină valoarea 4 în colțul triunghiular din stânga-sus (liniile 0-3, unde i+j <= 3) și în colțul triunghiular din dreapta-jos (liniile 5-8, unde i+j >= 13), și valoarea 2 în rest. O soluție: if(i+j<=3 || i+j>=13) a[i][j]=4; else a[i][j]=2; Barem, total 6 puncte: expresie de accesare a unui element al tabloului 1p; valori ale elementelor atribuite conform cerinței 4p (câte 2p pentru identificarea a cel puțin unei relații între valoarea elementului și poziția sa, respectiv pentru valorile corelate cu pozițiile folosind numărul indicat de atribuiri); corectitudine globală a secvenței 1p.

Pentru fiecare număr n din interval calculăm suma divizorilor proprii impari și suma celor pari; divizorii proprii sunt cei din intervalul [2, n/2] care divid n (excludem 1 și n).

int majImp(int a, int b)
{
    int n, d, sImpar, sPar;
    for (n = a; n <= b; n++)
    {
        sImpar = 0;
        sPar = 0;
        for (d = 2; d <= n / 2; d++)
            if (n % d == 0)
            {
                if (d % 2 == 0)
                    sPar = sPar + d;
                else
                    sImpar = sImpar + d;
            }
        if (sImpar > sPar)
            return n;
    }
    return 0;
}

Parcurgem intervalul crescător, deci primul număr găsit este cel mai mic; dacă bucla se încheie fără să găsim un număr major impar, returnăm 0. Verificare pe exemplu: pentru n=18, divizorii proprii sunt 2, 3, 6, 9, cu 3+9=12 > 2+6=8, deci se returnează 18.

Se cerea definiția completă în C/C++ a subprogramului majImp(a,b) care returnează cel mai mic număr din [a,b] (2 <= a <= b <= 10000) pentru care suma divizorilor proprii impari (divizori diferiți de 1 și de numărul însuși) este strict mai mare decât suma divizorilor proprii pari, sau 0 dacă nu există (exemplu: majImp(16,30)=18, pentru că 3+9 > 2+6). Barem, total 10 puncte: antet al subprogramului 2p (câte 1p pentru structură și parametri de intrare); determinare a valorii cerute 6p (câte 1p pentru: identificarea unui divizor par/impar, algoritm de bază pentru suma unei serii de valori, divizori suport pentru fiecare sumă, identificarea unui număr major impar, algoritm de bază pentru cel mai mic număr cu o proprietate dintr-o serie, numere suport verificate); instrucțiuni de returnare a rezultatului și tratare a cazului 0: 1p; declarare a variabilelor locale și corectitudine globală 1p.

Citim întregul rând (textul conține spații), apoi parcurgem caracterele și numărăm lungimea fiecărui cuvânt; prima lungime devine reper, iar orice lungime diferită invalidează proprietatea.

#include <iostream>
using namespace std;

int main()
{
    char s[101];
    cin.getline(s, 101);
    int n = -1, lg = 0, ok = 1, i;
    for (i = 0; s[i] != '\0'; i++)
    {
        if (s[i] == ' ')
        {
            if (n == -1) n = lg;
            else if (lg != n) ok = 0;
            lg = 0;
        }
        else
            lg++;
    }
    if (n == -1) n = lg;
    else if (lg != n) ok = 0;
    if (ok)
        cout << "DA " << n;
    else
        cout << "NU";
    return 0;
}

La fiecare spațiu comparăm lungimea cuvântului tocmai încheiat cu reperul n (prima lungime întâlnită); nu uităm ultimul cuvânt, care nu este urmat de spațiu. Pentru "Ana are cel mai bun mar" toate lungimile sunt 3, deci se afișează DA 3.

Se cerea un program C/C++ care citește un text de cel mult 100 de caractere (cuvinte din litere, separate prin câte un spațiu, cel puțin două cuvinte) și afișează DA urmat de n dacă toate cuvintele au câte n litere, altfel NU (exemplu: pentru "Ana are cel mai bun mar" se afișează DA 3). Barem, total 10 puncte: declarare a unei variabile care să permită memorarea unui text 1p; citire a datelor 1p; verificare a proprietății cerute 6p (câte 2p pentru: algoritm principial corect de verificare a unei proprietăți, determinarea lungimii unui cuvânt, cuvinte suport verificate); afișare a datelor în formatul cerut 1p; declarare a variabilelor simple și corectitudine globală 1p. Citirea trebuie făcută cu getline/cin.getline (textul conține spații).

Algoritm: parcurgem fișierul o singură dată. Păstrăm pentru scara curentă lungimea lgCrt și ultima cotă ultCrt, iar pentru cea mai lungă scară găsită lungimea lgMax și ultima sa cotă ultMax. Pentru fiecare număr x citit: dacă x = ultCrt + 1, scara curentă continuă (lgCrt crește cu 1); altfel începe o scară nouă (lgCrt = 1). După fiecare pas actualizăm ultCrt = x, iar dacă lgCrt > lgMax reținem lgMax = lgCrt și ultMax = x. La final, dacă lgMax < 2 nu există nicio scară și afișăm mesajul cerut; altfel afișăm numerele consecutive de la ultMax - lgMax + 1 până la ultMax.

Eficiență: timpul este liniar, O(n), fișierul fiind parcurs o singură dată, iar memoria este constantă, O(1): nu memorăm șirul (care poate avea $10^6$ elemente), ci doar câteva variabile simple, scara afișată fiind reconstituită din ultima cotă și lungime.

Pentru problema scării de lungime maximă (secvență de poziții consecutive cu cote numere consecutive strict crescătoare, într-un fișier cu cel mult 10^6 numere), se cerea descrierea în limbaj natural a unui algoritm eficient și justificarea eficienței. Soluția de referință: fișierul se parcurge o singură dată, memorând pentru scara curentă și pentru cea de lungime maximă doar lungimea (lgCrt, lgMax) și ultimul termen (ultCrt, ultMax); dacă numărul x citit continuă scara curentă (x = ultCrt+1) se incrementează lgCrt, altfel lgCrt devine 1; la fiecare pas se actualizează ultCrt = x și, dacă lgCrt > lgMax, lgMax și ultMax; scara maximă se reconstituie din ultMax și lgMax, iar mesajul nu exista se afișează dacă lgMax < 2. Eficiență: timp liniar O(n), memorie O(1) (nu se memorează șirul). Barem, total 2 puncte: coerența descrierii algoritmului 1p (se acordă chiar dacă algoritmul ales nu este eficient); justificarea elementelor de eficiență 1p.

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

int main()
{
    ifstream f("bac.txt");
    int x, ultCrt = 0, lgCrt = 0, lgMax = 0, ultMax = 0, c;
    while (f >> x)
    {
        if (x == ultCrt + 1)
            lgCrt++;
        else
            lgCrt = 1;
        ultCrt = x;
        if (lgCrt > lgMax)
        {
            lgMax = lgCrt;
            ultMax = x;
        }
    }
    f.close();
    if (lgMax < 2)
        cout << "nu exista";
    else
        for (c = ultMax - lgMax + 1; c <= ultMax; c++)
            cout << c << " ";
    return 0;
}

Programul parcurge fișierul o singură dată (timp liniar) și folosește doar câteva variabile simple (memorie constantă); scara de lungime maximă este reconstituită din ultima sa cotă și lungime. Pe exemplul dat, scările sunt 600-601, 569-570, 700-701 (lungime 2) și 625-627 (lungime 3), deci se afișează 625 626 627.

Se cerea programul C/C++ care rezolvă eficient problema scării de lungime maximă din fișierul bac.txt (cel mult 10^6 numere din [10,10^4]): afișează, în ordine strict crescătoare, cotele unei scări de lungime maximă, sau mesajul nu exista dacă nu există nicio scară (lungime minim 2). Soluție de referință: o singură parcurgere a fișierului cu variabilele lgCrt/ultCrt (scara curentă) și lgMax/ultMax (scara maximă); x continuă scara dacă x = ultCrt+1; afișarea finală enumeră lgMax numere consecutive începând cu ultMax-lgMax+1. 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 (se acordă numai 3p dacă algoritmul este principial corect, dar nu oferă rezultatul cerut pentru toate seturile de date); utilizare a unui algoritm eficient 1p (numai pentru un algoritm liniar, care utilizează eficient memoria, fără memorarea întregului șir); declarare a variabilelor, afișare a datelor, tratare a cazului nu exista și corectitudine globală 1p.