Bac informatică 2022 Model, rezolvat

Răspuns corect: a) !(x>20) || !(x<=22)

!(x>20) înseamnă x<=20, iar !(x<=22) înseamnă x>22, deci a) este chiar expresia dată. În b) rămâne x<20 && x<22, adică x<20, care este 0 pentru x=20; în c) rămâne x>22, tot 0 pentru x=20; în d) rămâne x>=20, care este 1 pentru x=21, deși expresia dată este 0.

Răspuns corect: d) f(18,19,r);

Subprogramul înjumătățește ambele numere până când sunt amândouă impare; abia atunci z devine 1 și, la fiecare revenire din apel, crește cu 1. Așadar r este 1 plus numărul de apeluri recursive. La f(18,19,r) se coboară o singură dată — 18 este par, iar 9 și 9 sunt amândouă impare — deci r ajunge 2. La a) și b) se coboară de două ori (r=3), iar la c) de patru ori (r=5).

Răspuns corect: b) (drajeuri, jeleuri)

Soluțiile se generează în ordinea tipurilor din mulțime, iar jeleurile și pralinele nu pot apărea împreună: (bomboane, drajeuri), (bomboane, drajeuri, jeleuri), (bomboane, drajeuri, praline), (bomboane, jeleuri), (bomboane, praline), (drajeuri, jeleuri). A șasea este (drajeuri, jeleuri). Combinațiile (bomboane, jeleuri, praline) și (jeleuri, praline) sunt sărite, pentru că au și jeleuri, și praline.

Răspuns corect: c) 24

Un graf neorientat fără cicluri cu n noduri și c componente conexe are exact n-c muchii: fiecare componentă este un arbore, iar un arbore cu k noduri are k-1 muchii. Din 22 = n-2 rezultă n = 24.

Răspuns corect: c) 4044

Pe diagonala secundară a unui tablou cu n linii și n coloane, numerotate începând de la 0, suma indicilor unui element este n-1. Din 2021 + 2022 = n-1 rezultă n = 4044.

Răspunsul din barem: 1*1 5*2

Pentru k=2: [√2] este 1, deci s=1; fiind primul afișaj (u=0), se scrie 1*1, apoi u=1 și nr=0. Pentru k=3: [√3] este tot 1, deci s=1=u și nu se afișează nimic. Pentru k=4: [√4] este 2, deci s=1+4=5; cum 5≠1, se scrie 5*2 (nr numărase 3 și 4), apoi u=5. Pentru k=5, 6 și 7: [√k] rămâne 2, deci s=5=u și nu se mai afișează nimic.

Exemplu: 16 și 20

Se afișează o singură dată, la primul k, iar valoarea scrisă trebuie să fie 30: suma 1²+2²+3²+4² se obține când [√k] este 4, adică pentru k între 16 și 24. Primul k este chiar x, iar nr este atunci 1, deci se scrie 30*1. Pentru ca după aceea să nu se mai afișeze nimic, s trebuie să rămână 30 până la y=22, ceea ce se întâmplă pentru orice k≤24. Cum enunțul cere x<y, x poate fi orice număr din mulțimea {16, 17, 18, 19, 20, 21}.

#include <iostream>
using namespace std;

int main()
{
    int x, y, u = 0, nr = 0;
    cin >> x >> y;
    for (int k = x; k <= y; k++)
    {
        int s = 0;
        nr = nr + 1;
        // t ≤ [√k], scris fără sqrt: la un pătrat perfect virgula mobilă poate
        // întoarce 6,999… în loc de 7, iar suma ar pierde ultimul termen.
        for (int t = 1; t * t <= k; t++)
            s = s + t * t;
        if (s != u)
        {
            cout << s << '*' << nr << ' ';
            u = s;
            nr = 0;
        }
    }
    return 0;
}

citește x,y (numere naturale, x<y)
 u←0; nr←0
┌pentru k←x,y execută
│ s←0; nr←nr+1
│ t←1
│┌cât timp t≤[√k] execută
││ s←s+t*t
││ t←t+1
│└■
│┌dacă s≠u atunci
││ scrie s,'*',nr,' '
││ u←s; nr←0
│└■
└■

Structura pentru ținea singură contorul: îl pornea de la 1, îl compara cu [√k] și îl creștea. Înlocuită cu cât timp, cele trei lucruri se scriu separat — t←1 înaintea buclei, condiția t≤[√k] în antet și t←t+1 la sfârșitul corpului. Inițializarea stă în interiorul buclei după k, pentru că t trebuie să pornească din nou de la 1 la fiecare k.

Răspunsul din barem: 1,7,8

Vectorul de „tați" ține pe poziția i eticheta părintelui nodului i. Fiii nodului 3 sunt nodurile care au valoarea 3 pe poziția lor: poziția 1 (3), poziția 7 (3) și poziția 8 (3).

struct zbor
{
    int cod;
    struct
    {
        int ora, minut;
    } aterizare;
    int durata;
} z;

Structura are câte un câmp pentru fiecare dată din enunț: codul, momentul aterizării și durata. Momentul aterizării e format din două numere, ora și minutul, iar expresia din enunț le folosește ca z.aterizare.ora și z.aterizare.minut — deci aterizare e la rândul ei o structură. Variabila z se declară odată cu definirea structurii.

int cmmdc(int a, int b)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int mozaic(int x, int y, int z)
{
    int m = x / cmmdc(x, y) * y;
    return m / cmmdc(m, z) * z;
}

Cele trei benzi au aceeași lungime, iar fiecare e formată din plăcuțe întregi de un singur tip: lungimea mozaicului trebuie să fie multiplu și al lui x, și al lui y, și al lui z. Cea mai mică lungime posibilă este deci cel mai mic multiplu comun al celor trei numere. Se calculează din doi în doi, cu algoritmul lui Euclid: x*y/cmmdc(x,y), iar rezultatul cu z. Împărțirea se face înaintea înmulțirii, ca produsul să nu depășească domeniul lui int.

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

int main()
{
    char s[101];
    cin.getline(s, 101);
    int k = 0, toate = 1;
    for (char *p = strtok(s, " "); p != NULL; p = strtok(NULL, " "))
        if (p[0] >= '0' && p[0] <= '9')
        {
            int cifre = strlen(p);
            if (k == 0) k = cifre;
            else if (cifre != k) toate = 0;
        }
    if (toate) cout << k;
    else cout << "NU";
    return 0;
}

Textul se citește întreg, cu spații, deci cin.getline. strtok îl taie în cuvinte după spații, iar un cuvânt care începe cu o cifră este un număr — cuvintele propriu-zise au numai litere mici. Numărul de cifre este chiar lungimea acelui cuvânt. Primul număr întâlnit dă k; dacă vreunul de după are altă lungime, răspunsul devine NU.

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

Se citește șirul o singură dată. Pentru fiecare dintre cele zece valori posibile se ține minte poziția pe care a apărut prima oară (prim[v]). Când se citește un termen par x aflat pe poziția i, secvența par-încadrată cea mai lungă care se termină aici începe la prim[x], deci are lungimea i-prim[x]+1. Se păstrează lungimea maximă și valorile care o dau: la o lungime mai mare lista se golește și rămâne doar x, la una egală x se adaugă.

Algoritmul parcurge șirul o singură dată și nu îl memorează: face un număr de operații proporțional cu numărul de termeni și folosește doar zece poziții suplimentare, oricât de lung ar fi șirul.

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

int main()
{
    ifstream f("bac.txt");
    int prim[10], da[10] = {0}, x, i = 0, maxim = 0;
    for (int v = 0; v < 10; v++) prim[v] = -1;
    while (f >> x)
    {
        if (x % 2 == 0)
        {
            if (prim[x] == -1) prim[x] = i;
            int lung = i - prim[x] + 1;
            if (lung > maxim)
            {
                maxim = lung;
                for (int v = 0; v < 10; v++) da[v] = 0;
                da[x] = 1;
            }
            else if (lung == maxim) da[x] = 1;
        }
        i++;
    }
    f.close();
    cout << maxim << "\n";
    for (int v = 0; v < 10; v++)
        if (da[v]) cout << v << " ";
    return 0;
}