subac

Bac informatică 2023 Varianta 6, rezolvată

Lucrarea „2023 Varianta 6” 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
IIIIII

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

  1. Exercițiul 14p

    Variabilele întregi m și n memorează câte un număr natural.

    Indicați expresia C/C++ care are valoarea 1 dacă și numai dacă fiecare dintre numerele memorate în variabilele m și n este par.

    • a)(m+n)%2==0
    • b)(m-n)%2==0
    • c)m%2+n%2==0
    • d)m%2-n%2==0
    Arată răspunsul și explicația

    Răspuns corect: c) m%2+n%2==0

    m%2 și n%2 sunt 0 sau 1, deci suma lor este 0 doar când amândouă sunt 0, adică atunci când ambele numere sunt pare.

    a), b) și d) sunt adevărate când numerele au aceeași paritate, deci și când amândouă sunt impare (de exemplu 1 și 3).

  2. Exercițiul 24p

    Subprogramul f este definit alăturat.

    Indicați valoarea f(35,3).

    int f(int n,int k)
{ if(n==0 || k==0) return 0;
  return n%k+10*f(n/k,k);
}
    • a)1022
    • b)355
    • c)102
    • d)33
    Arată răspunsul și explicația

    Răspuns corect: a) 1022

    f(n,k) ia ultima cifră a lui n în baza k (n%k) și pune în fața ei, înmulțit cu 10, rezultatul pentru n/k: construiește scrierea lui n în baza k, citită ca număr în baza 10.

    35 = 1·27 + 0·9 + 2·3 + 2, deci scrierea lui 35 în baza 3 este 1022, iar f(35,3) = 1022.

  3. Exercițiul 34p

    Variabila p, declarată alăturat, memorează dimensiunile unui paralelipiped dreptunghic: lungimea, lățimea, respectiv înălțimea.

    Volumul paralelipipedului este egal cu produsul celor trei dimensiuni ale sale.

    Indicați o instrucțiune prin care i se atribuie variabilei reale v valoarea volumului paralelipipedului corespunzător variabilei p.

    struct paralelipiped
{  float lg,lt,h;
}p;
    • a)v=lg*lt*h;
    • b)v=lg.p*lt.p*h.p;
    • c)v=p(lg*lt*h);
    • d)v=p.lg*p.lt*p.h;
    Arată răspunsul și explicația

    Răspuns corect: d) v=p.lg*p.lt*p.h;

    Câmpurile se accesează prin variabila p: p.lg, p.lt și p.h, iar volumul este produsul lor: v=p.lg*p.lt*p.h;.

    a) folosește câmpurile fără variabilă, iar b) și c) nu sunt instrucțiuni C/C++ valide.

  4. Exercițiul 44p

    Utilizând metoda bactracking se generează toate șirurile de 5 litere distincte din mulțimea {A, M, U, R, G}, astfel încât în fiecare șir litera R precede literele A și M. Primele cinci soluții generate sunt, în această ordine:

    1. URAMG
    2. URAGM
    3. URMAG
    4. URMGA
    5. URGAM

    Indicați soluția generată imediat după GURMA.

    • a)GARUM
    • b)GRAMU
    • c)GRAUM
    • d)GRUAM
    Arată răspunsul și explicația

    Răspuns corect: b) GRAMU

    Literele se încearcă în ordinea din mulțime, A, M, U, R, G, iar R trebuie să apară înaintea lui A și a lui M.

    După GURMA nu mai există altă continuare pentru prefixul GU: pe poziția a treia, după R, ar urma doar G, deja folosit. Se schimbă deci a doua literă: după U vine R. Cu prefixul GR, celelalte litere se pun în ordinea cea mai mică, A, M, U, iar R este înaintea lui A și a lui M: GRAMU.

  5. Exercițiul 54p

    Într-o zonă sunt 23 de obiective turistice, numerotate de la 1 la 23; zona este reprezentată ca un graf orientat în care vârfurile corespund acestor obiective, iar arcele sunt stabilite în funcție de modalitatea de deplasare între două obiective, astfel: de la fiecare obiectiv numerotat cu i (i∈[1,23]) se poate merge direct doar la obiectivul numerotat cu 2*i, dacă acesta există, sau doar la obiectivul numerotat cu i-1, în caz contrar.

    Indicați numărul maxim de vârfuri ale unui drum elementar în acest graf, cu extremitatea inițială 1.

    • a)5
    • b)11
    • c)16
    • d)21
    Arată răspunsul și explicația

    Răspuns corect: c) 16

    Din fiecare vârf pleacă exact un arc (spre 2·i, dacă există, altfel spre i−1), deci drumul care pornește din 1 este unic: se merge pe el până se ajunge într-un vârf deja vizitat.

    1 → 2 → 4 → 8 → 16 → 15 → 14 → 13 → 12 → 11 → 22 → 21 → 20 → 19 → 18 → 17, iar din 17 s-ar ajunge în 16, deja vizitat. Drumul elementar are 16 vârfuri.

Subiectul al II-lea40 de puncte

  1. Exercițiul 1.a6p

    Algoritmul alăturat este reprezentat în pseudocod.

    Scrieți ce se afișează în urma executării algoritmului, dacă se citește numărul 3.

    citește n
    (număr natural nenul)
┌pentru i←1,n execută
│┌pentru j←1,n execută
││┌dacă j≤i atunci
│││  scrie 2
│││altfel
│││  scrie 3
││└■
│└■
└■
    Arată răspunsul și explicația

    Răspunsul din barem: 233223222

    233223222

Pentru fiecare rând i și fiecare coloană j, ambele de la 1 la n, se scrie 2 dacă j≤i, altfel 3, fără spații între cifre. Pentru n=3: rândul 1 dă 233, rândul 2 dă 223, iar rândul 3 dă 222.

  2. Exercițiul 1.b6p

    Algoritmul alăturat este reprezentat în pseudocod.

    Scrieți două numere care pot fi citite, astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, în total, numărul de cifre 2 afișate să fie în intervalul [20,50].

    citește n
    (număr natural nenul)
┌pentru i←1,n execută
│┌pentru j←1,n execută
││┌dacă j≤i atunci
│││  scrie 2
│││altfel
│││  scrie 3
││└■
│└■
└■
    Arată răspunsul și explicația
    Exemplu: 6 9

Pe rândul i se scrie de i ori cifra 2, deci în total se scriu 1 + 2 + … + n = n·(n+1)/2 cifre 2. Valoarea este în intervalul [20,50] pentru n = 6 (21), 7 (28), 8 (36) și 9 (45).

  3. Exercițiul 1.c10p

    Algoritmul alăturat este reprezentat în pseudocod.

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

    citește n
    (număr natural nenul)
┌pentru i←1,n execută
│┌pentru j←1,n execută
││┌dacă j≤i atunci
│││  scrie 2
│││altfel
│││  scrie 3
││└■
│└■
└■
    Arată răspunsul și explicația
    #include <iostream>
using namespace std;

int main()
{
    int n, i, j;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (j <= i) cout << 2;
            else cout << 3;
    return 0;
}

Cele două structuri pentru devin for, iar dacă…altfel devine if…else. Cifrele se afișează una după alta, fără spații, ca în algoritm.

  4. Exercițiul 1.d6p

    Algoritmul alăturat este reprezentat în pseudocod.

    Scrieți în pseudocod un algoritm, echivalent cu cel dat, înlocuind una dintre structurile pentru...execută cu o structură de tip cât timp...execută.

    citește n
    (număr natural nenul)
┌pentru i←1,n execută
│┌pentru j←1,n execută
││┌dacă j≤i atunci
│││  scrie 2
│││altfel
│││  scrie 3
││└■
│└■
└■
    Arată răspunsul și explicația
    citește n (număr natural nenul)
i←1
┌cât timp i≤n execută
│┌pentru j←1,n execută
││┌dacă j≤i atunci
│││ scrie 2
│││altfel
│││ scrie 3
││└■
│└■
│ i←i+1
└■

A fost înlocuită prima structură pentru. Cu cât timp, contorul i se gestionează explicit: primește valoarea inițială 1 înainte de buclă, se continuă cât timp i≤n, iar i←i+1 se face la sfârșitul corpului.

  5. Exercițiul 26p

    Un arbore cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de „tați" (0,1,1,2,2,4,5,1). Enumerați toți descendenții nodului numerotat cu 2.

    Arată răspunsul și explicația

    Răspunsul din barem: 4, 5, 6, 7

    4, 5, 6, 7

Fiii lui 2 sunt nodurile care au în vector valoarea 2, adică 4 și 5. Fiul lui 4 este 6, iar fiul lui 5 este 7, iar aceștia nu mai au fii. Descendenții lui 2 sunt toți: 4, 5, 6 și 7, în orice ordine.

  6. Exercițiul 36p

    Un șir de caractere a este numit prefix al unui șir de caractere b dacă este identic cu b sau dacă b se obține din a prin adăugarea la dreapta a unor alte caractere.

    Variabila k este de tip întreg, iar variabila s permite accesul la un șir de cel mult 20 de caractere.

    Scrieți secvența de instrucțiuni de mai jos, înlocuind punctele de suspensie astfel încât, în urma executării secvenței obținute, să se afișeze pe ecran, în ordinea descrescătoare a lungimii, separate prin câte un spațiu, toate prefixele șirului accesat prin variabila s, fiecare încheindu-se cu prima literă a șirului s, ca în exemplu. Declarați eventualele alte variabile utilizate.

    Exemplu: pentru șirul elemente se afișează: elemente eleme ele e

    for(k=strlen(s)-1;k>=0;k--)
{..................}
    Arată răspunsul și explicația
    for(k=strlen(s)-1;k>=0;k--)
{ if(s[k]==s[0])
  { char c=s[k+1];
    s[k+1]='\0';
    cout<<s<<' ';
    s[k+1]=c;
  }
}

Un prefix care se încheie cu prima literă a lui s se termină pe o poziție k unde s[k] este egală cu s[0]. Pozițiile se parcurg de la ultima la prima, deci prefixele ies în ordinea descrescătoare a lungimii. Ca să se afișeze doar prefixul, terminatorul de șir se pune temporar pe poziția k+1, iar caracterul de acolo, păstrat în c, se pune la loc după afișare.

Subiectul al III-lea30 de puncte

  1. Exercițiul 110p

    Subprogramul Putere are trei parametri:

    • n, prin care primește un număr natural (n∈[2,109]);

    • x și p, prin care furnizează două numere naturale cu proprietatea că n=xp, iar x este cel mai mic număr cu această proprietate.

    Scrieți definiția completă a subprogramului.

    Exemplu: dacă n=16 atunci, după apel, x=2 și p=4, dacă n=216 atunci, după apel, x=6 și p=3, iar dacă n=12 atunci, după apel, x=12 și p=1.

    Arată răspunsul și explicația
    void Putere(int n, int &x, int &p)
{
    int b, m, k;
    for (b = 2; b * b <= n; b++)
    {
        m = n;
        k = 0;
        while (m % b == 0)
        {
            m = m / b;
            k++;
        }
        if (m == 1)
        {
            x = b;
            p = k;
            return;
        }
    }
    x = n;
    p = 1;
}

Bazele posibile se încearcă în ordine crescătoare. Pentru o bază b, n se împarte la b de câte ori se poate; dacă rămâne 1, n este o putere a lui b, cu exponentul egal cu numărul de împărțiri, iar b este cea mai mică bază, fiindcă cele mai mici au fost încercate înainte. O bază mai mare decât radicalul lui n ar da exponentul 1, deci, dacă nu s-a găsit nimic, x = n și p = 1.

  2. Exercițiul 210p

    La o expoziție sunt prezentate mai multe tipuri de flori, fiecare având un anumit cod. Zona de expunere este organizată pe n rânduri, fiecare având câte n parcele de dimensiune egală. Pe primul rând sunt expuse n tipuri de flori distincte, fiecare parcelă conținând flori de un anumit tip. Celelalte parcele sunt ocupate astfel:

    • toate parcelele aflate în dreapta diagonalei secundare a zonei de expunere sunt ocupate de gazon;

    • fiecare parcelă, aflată pe diagonala secundară a zonei de expunere sau în stânga acestei diagonale, conține flori cu un cod de cel mult două cifre, obținut din ultimele două cifre ale sumei codurilor florilor aflate în două parcele de pe rândul anterior, și anume cea de pe aceeași coloană, respectiv cea de pe coloana din dreapta sa; dacă prima dintre cifrele codului obținut este 0, ea este ignorată, ca în exemplu.

    Scrieți un program C/C++ care citește de la tastatură un număr natural, n (n∈[2,20]), apoi n numere naturale distincte din intervalul [0,102), reprezentând, în această ordine, de la stânga la dreapta, codurile florilor din parcelele aflate pe primul rând al zonei de expunere; gazonul are codul -1. Programul construiește în memorie un tablou bidimensional cu n linii și n coloane, în care fiecare linie corespunde unui rând de parcele și fiecare element al liniei corespunde unei parcele, în ordinea acestora, și memorează codul plantelor (flori sau gazon) plasate în acea parcelă.

    Programul afișează pe ecran tabloul obținut, fiecare linie a tabloului pe câte o linie a ecranului, elementele de pe aceeași linie fiind separate prin câte un spațiu.

    Exemplu: dacă se citesc numerele n=5, apoi 90, 10, 4, 27, 30 se obține tabloul alăturat.

    Figura din enunț
    Arată răspunsul și explicația
    #include <iostream>
using namespace std;

int main()
{
    int n, a[20][20], i, j;
    cin >> n;
    for (j = 0; j < n; j++)
        cin >> a[0][j];
    for (i = 1; i < n; i++)
        for (j = 0; j < n; j++)
            if (i + j <= n - 1) a[i][j] = (a[i - 1][j] + a[i - 1][j + 1]) % 100;
            else a[i][j] = -1;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

Numerotând de la 0, o parcelă (i,j) este pe diagonala secundară sau în stânga ei când i + j ≤ n − 1; în dreapta ei este gazon, cu codul -1. Pentru o parcelă cu flori de pe un rând i ≥ 1, codul este restul împărțirii la 100 al sumei parcelelor de deasupra ei și din dreapta acesteia; restul la 100 păstrează ultimele două cifre și ignoră automat un 0 de la început. Pe rândul anterior, coloana j+1 este tot în zona cu flori, deci suma se face mereu între două coduri de flori.

  3. Exercițiul 3.a2p

    Intervalul [x,y] se numește p-interval pentru un șir de valori întregi, dacă oricare dintre primii p termeni ai șirului aparține intervalului, iar numărul de valori întregi distincte din interval este minim.

    Exemplu: pentru șirul 2, 7, -1, 8, 3, 10 există [2,2] ca 1-interval, [-1,8] ca 4-interval și 5-interval etc. Fișierul bac.in conține un șir de cel mult 106 numere întregi din intervalul [-109,109], separate prin câte un spațiu.

    Se cere să se afișeze pe ecran cea mai mică și cea mai mare valoare a lui p (p≥2) cu proprietatea că (p-1)-interval este identic cu p-interval pentru șirul aflat în fișier. Valorile afișate pot fi egale, iar dacă nu există nicio astfel de valoare, pe ecran se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.

    Exemplu: dacă fișierul conține numerele 2 7 1 8 3 10 6 -3 -2 13, se afișează pe ecran 5 9 (intervale conform cerinței se obțin pentru valorile 5, 7 și 9 ale lui p), iar dacă fișierul conține numerele 2 7 1 0 8 10 -3 13, se afișează pe ecran nu exista

    Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.

    Arată răspunsul și explicația
    p-intervalul primilor p termeni este [minimul lor, maximul lor]. (p−1)-intervalul este identic cu p-intervalul exact când al p-lea termen nu schimbă nici minimul, nici maximul, adică se află deja în intervalul [min, max] al termenilor dinaintea lui.

Termenii se citesc pe rând, fără să fie memorați, păstrându-se minimul și maximul de până atunci și poziția curentă p. Pentru fiecare termen de la al doilea încolo: dacă se află între minim și maxim, p este o valoare potrivită — dacă este prima găsită, se reține ca pmin, iar în orice caz devine pmax. Apoi se actualizează minimul și maximul. La final se afișează pmin și pmax sau nu exista, dacă nu s-a găsit nicio valoare.

Eficiență: fiecare termen se prelucrează o singură dată, în timp constant, deci algoritmul este liniar în numărul de termeni; se folosesc doar câteva variabile simple, deci memoria este constantă.

  4. Exercițiul 3.b8p

    Intervalul [x,y] se numește p-interval pentru un șir de valori întregi, dacă oricare dintre primii p termeni ai șirului aparține intervalului, iar numărul de valori întregi distincte din interval este minim.

    Exemplu: pentru șirul 2, 7, -1, 8, 3, 10 există [2,2] ca 1-interval, [-1,8] ca 4-interval și 5-interval etc. Fișierul bac.in conține un șir de cel mult 106 numere întregi din intervalul [-109,109], separate prin câte un spațiu.

    Se cere să se afișeze pe ecran cea mai mică și cea mai mare valoare a lui p (p≥2) cu proprietatea că (p-1)-interval este identic cu p-interval pentru șirul aflat în fișier. Valorile afișate pot fi egale, iar dacă nu există nicio astfel de valoare, pe ecran se afișează mesajul nu exista. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.

    Exemplu: dacă fișierul conține numerele 2 7 1 8 3 10 6 -3 -2 13, se afișează pe ecran 5 9 (intervale conform cerinței se obțin pentru valorile 5, 7 și 9 ale lui p), iar dacă fișierul conține numerele 2 7 1 0 8 10 -3 13, se afișează pe ecran nu exista

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

    Arată răspunsul și explicația
    #include <fstream>
#include <iostream>
using namespace std;

int main()
{
    ifstream fin("bac.in");
    int x, p = 0, pmin = 0, pmax = 0, minc = 1000000001, maxc = -1000000001;
    while (fin >> x)
    {
        p++;
        if (x >= minc && x <= maxc)
        {
            if (pmin == 0) pmin = p;
            pmax = p;
        }
        if (x < minc) minc = x;
        if (x > maxc) maxc = x;
    }
    fin.close();
    if (pmin == 0) cout << "nu exista";
    else cout << pmin << ' ' << pmax;
    return 0;
}

Programul face pașii de la 3.a. Minimul pornește de la o valoare mai mare decât orice termen, iar maximul de la una mai mică, deci primul termen nu poate fi în interval și le stabilește pe amândouă.

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