Bac informatică 2023 Varianta 7, rezolvată

Răspuns corect: b) x=25 și y=15

Pentru x=25 și y=15: y%x este 15, x/y este 1, iar 15 − 1·3 = 12, diferit de 0, deci expresia are valoarea 1.

În a) și d), y%x și x/y sunt amândouă 0, deci diferența este 0, iar c) împarte la y=0, ceea ce nu e permis.

Răspuns corect: c) 9

Funcția calculează x la puterea y prin înjumătățirea exponentului. f(3,1) folosește f(3,0) = 1 și, cum 1 este impar, returnează 1·1·3 = 3. f(3,2) folosește f(3,1) = 3 și, cum 2 este par, returnează 3·3 = 9.

Răspuns corect: a) 20123

După strcpy(s,"2019"), s+3 indică poziția cifrei 9. strcpy(s+3,"23") scrie de acolo „23” și terminatorul de șir, deci primele trei caractere, „201”, rămân neschimbate, iar șirul devine 20123.

Răspuns corect: b) (cireș, lămâie, salcâm)

Parfumurile sunt submulțimi de trei esențe, generate în ordinea din mulțime, deci ultimele încep cu esențele cele mai târzii. Ultima soluție este (iris, lămâie, salcâm), iar chiar înaintea ei vine ultima soluție care începe cu cireș: (cireș, lămâie, salcâm).

c) nu respectă ordinea din mulțime (lămâie înaintea lui iris), deci nu este generată deloc.

Răspuns corect: d) 3 și 3

Suma gradelor este dublul numărului de muchii, deci pară, iar într-un graf cu 5 noduri un grad este cel mult 4.

b) are gradul 5; c) dă suma 2 + 2 + 3 + 3 + 3 = 13, impară; în a), nodul de grad 4 ar fi legat de toate celelalte, deci niciun nod n-ar putea avea gradul 0. Rămâne d): de exemplu, din graful complet cu 5 noduri se elimină muchiile [1,2], [1,3] și [4,5], iar gradele devin 2, 3, 3, 3, 3.

Răspunsul din barem: 2

Pentru fiecare pereche (a,b), algoritmul păstrează doar prima cifră a lui a, pe poziția ei (p este puterea lui 10 corespunzătoare), și îi adaugă b; x numără perechile pentru care rezultatul diferă de a. Rezultatul este egal cu a exact când b este chiar a fără prima cifră. (746, 82): 700 + 82 = 782, diferit de 746; (3067, 67): 3000 + 67 = 3067, egal; (78, 178): 70 + 178 = 248, diferit de 78. Se afișează 2.

Exemplu: 5 0 7 0

Pentru un număr a de o cifră, p rămâne 1, iar rezultatul este a + b, egal cu a doar dacă b = 0. Cu n=2 se citesc două perechi, deci șirul are forma x, 0, y, 0, cu x și y din intervalul [0,9].

#include <iostream>
using namespace std;

int main()
{
    int n, x = 0, a, b, c, p;
    cin >> n;
    while (n > 0)
    {
        cin >> a >> b;
        c = a;
        p = 1;
        while (a > 9)
        {
            a = a / 10;
            p = p * 10;
        }
        a = a * p + b;
        if (a != c) x = x + 1;
        n = n - 1;
    }
    cout << x;
    return 0;
}

Cele două structuri cât timp devin while, iar [a/10] este împărțirea întreagă din C/C++. a și b se citesc la fiecare pas al buclei exterioare, ca în algoritm.

citește n (număr natural nenul)
x←0
┌pentru i←1,n execută
│ citește a,b (numere naturale)
│ c←a; p←1
│┌cât timp a>9 execută
││ a←[a/10]; p←p*10
│└■
│ a←a*p+b
│┌dacă a≠c atunci
││ x←x+1
│└■
└■
scrie x

n era folosit doar ca un contor care scade până la 0, deci bucla se executa de n ori. Structura pentru, cu un contor nou i de la 1 la n, face același număr de pași, iar instrucțiunea n←n-1 dispare.

Răspunsul din barem: 2, 3

Numărul de niveluri este cel mai mic atunci când rădăcina este cât mai la mijlocul arborelui. Cu rădăcina 2, nodurile cele mai îndepărtate (4 și 5) sunt la distanța 2, deci arborele are 3 niveluri; la fel cu rădăcina 3, pentru care cele mai îndepărtate sunt 1 și 6. Orice altă rădăcină are un nod la distanța 3 sau mai mare (de exemplu, din 1 până la 4), deci cel puțin 4 niveluri.

if (p.pret < 100) a = p.denumire[0];
else a = '*';

Prima literă a denumirii este primul caracter al șirului, p.denumire[0]. Caracterul * se scrie între apostrofuri, ca o constantă de tip caracter.

void DNPI(int n)
{
    int d, v, k, t, prim;
    for (d = 1; d * d <= n; d++)
        if (n % d == 0)
            for (t = 1; t <= 2; t++)
            {
                if (t == 1) v = d;
                else v = n / d;
                if (t == 2 && v == d) break;
                if (v % 2 == 1)
                {
                    prim = 1;
                    if (v < 2) prim = 0;
                    for (k = 2; k * k <= v; k++)
                        if (v % k == 0) prim = 0;
                    if (prim == 0) cout << v << ' ';
                }
            }
}

Divizorii lui n se iau în perechi, d și n/d, cu d până la radicalul lui n (când d = n/d, divizorul se ia o singură dată). Pentru fiecare divizor impar se verifică dacă este prim; 1 nu este prim, deci se afișează și el. Enunțul acceptă numerele în orice ordine.

#include <iostream>
using namespace std;

int main()
{
    int m, n, a[20][20], i, j, s, maxim = -1;
    cin >> m >> n;
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
            cin >> a[i][j];
    for (i = 0; i + 1 < m; i++)
        for (j = 0; j + 1 < n; j++)
        {
            s = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
            if (s > maxim) maxim = s;
        }
    cout << maxim;
    return 0;
}

Un pătrat este determinat de celula lui din stânga-sus, (i,j), care poate fi pe orice linie în afară de ultima și pe orice coloană în afară de ultima. Pentru fiecare se calculează suma celor patru celule și se reține cea mai mare. Valorile sunt naturale, deci maxim poate porni de la -1.

Timp de executare: O(n) · Memorie: O(1)

Fiecare poziție poate apărea în cel mult o pereche, iar o pereche leagă doi termeni egali. Pentru o valoare v care apare de a ori în A și de b ori în B se pot forma cel mult min(a, b) perechi cu valoarea v, și chiar atâtea. Răspunsul este suma acestor minime, pentru toate valorile.

Valorile sunt între 0 și 99, deci se folosesc doi vectori de frecvență cu câte 100 de elemente: pe măsura citirii lui A crește fa[v], iar pe măsura citirii lui B crește fb[v]. La final se adună min(fa[v], fb[v]) pentru v de la 0 la 99.

Eficiență: fiecare număr se citește și se numără o singură dată, în timp constant, iar suma finală are un număr fix de pași, deci timpul este liniar în numărul de valori din fișier.

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

int main()
{
    ifstream fin("date.in");
    int fa[100] = {0}, fb[100] = {0}, m, n, i, v, nr = 0;
    fin >> m >> n;
    for (i = 0; i < m; i++)
    {
        fin >> v;
        fa[v]++;
    }
    for (i = 0; i < n; i++)
    {
        fin >> v;
        fb[v]++;
    }
    fin.close();
    for (v = 0; v < 100; v++)
        if (fa[v] < fb[v]) nr = nr + fa[v];
        else nr = nr + fb[v];
    cout << nr;
    return 0;
}

Programul face pașii de la 3.a. Numărul perechilor este cel mult 10^{^6} și încape în tipul int.