Bac informatică 2021 Simulare, rezolvată

Răspuns corect: c) [2002,2020]

Se scapă de negații, una câte una:

• !(x<2001) înseamnă x≥2001
• !(x<2002 || x>2020) înseamnă x≥2002 și x≤2020
• !(x>2021) înseamnă x≤2021

Toate trei trebuie să fie adevărate deodată. Condiția din mijloc e cea mai strânsă: ea cere deja x≥2002, mai mult decât prima, și x≤2020, mai mult decât a treia.

Rămâne intervalul [2002, 2020], varianta c).

Răspuns corect: a) al 10-lea

Backtracking-ul construiește numerele cifră cu cifră, folosind doar cifrele 2, 8 și 9, și reține fiecare valoare mai mică decât 289. Un număr se prelungește doar cât timp rămâne sub 289:

Primele șase coincid cu cele din enunț. 8 este deci al 10-lea, varianta a).

Răspuns corect: c) s.vizite.nrAccesari=2*s.vizite.nrAprecieri;

Structura are un câmp simplu, cod, și un câmp vizite care e la rândul lui o structură cu nrAccesari și nrAprecieri. Accesul se face punct după punct, de la variabilă spre câmpul dorit: s.vizite.nrAccesari — varianta c) e corectă sintactic.

Celelalte greșesc fiecare altceva: a) folosește paranteze, ca la un apel de funcție; b) încearcă să atribuie toată structura dintr-o listă de valori, ceea ce nu se poate așa; d) pune numele tipului (site) în mijlocul accesului, deși după s. urmează direct numele câmpului.

Răspuns corect: d) x-y>0

Subprogramul e algoritmul lui Euclid prin scăderi repetate: din cel mai mare se scade cel mai mic, până când cele două devin egale — iar atunci valoarea comună e cel mai mare divizor comun.

Pentru ca scăderea să meargă în direcția bună, ramura f(x-y,y) trebuie aleasă exact când x e mai mare decât y, adică atunci când x-y>0 — varianta d).

Celelalte n-ar merge: a) și b) se uită la cifrele lui x, fără legătură cu comparația, iar c) e adevărată aproape mereu, deci s-ar scădea y din x chiar și când x<y, iar numerele ar fugi spre valori negative în loc să se apropie.

Răspuns corect: b) 35

Un arbore cu k noduri are k-1 muchii.

Graful are 5 componente conexe, fiecare fiind arbore. Dacă ele au k₁, k₂, …, k₅ noduri, cu k₁+…+k₅ = 40, atunci numărul total de muchii este:

`(k₁-1) + (k₂-1) + … + (k₅-1) = 40 - 5 = 35`

Varianta b). Observă că nu contează cum sunt împărțite nodurile între componente — se scade câte 1 pentru fiecare componentă, și atât.

Răspunsul din barem: 2197553

Algoritmul ia cifrele lui x de la dreapta la stânga, sare peste zerouri și așază fiecare cifră fie la coadă, fie în față, după cum e mai mică sau nu decât cifra dinaintea ei în număr.

Se afișează 2197553. Zeroul din 35210579 nu apare deloc în rezultat, iar p nu crește când se sare peste el.

2012 2201

Sunt exact trei numere de patru cifre care dau 212: 2012, 2201 și 2210.

Urmărește 2012 — cifrele se iau de la dreapta, iar fiecare se compară cu cifra rămasă imediat în stânga ei:

Toate cifrele nenule au ajuns la coadă, în ordinea în care au fost citite, iar zeroul a fost sărit. Așa se obține 212.

2201 și 2210 ajung la același rezultat pe alt drum: contează care cifre sunt nenule și cum se compară fiecare cu vecina din stânga.

#include <iostream>
using namespace std;

int main()
{
    int x, p = 1, y = 0, c;
    cin >> x;
    do
    {
        c = x % 10;
        x = x / 10;
        if (c != 0)
        {
            if (x % 10 < c)
                y = y * 10 + c;
            else
                y = c * p + y;
            p = p * 10;
        }
    } while (x != 0);
    cout << y;
    return 0;
}

`` citește x (număr natural) p←1; y←0 c←x%10; x←[x/10] ┌dacă c≠0 atunci │┌dacă x%10<c atunci y←y*10+c ││altfel y←c*p+y │└■ │ p←p*10 └■ ┌cât timp x≠0 execută │ c←x%10; x←[x/10] │┌dacă c≠0 atunci ││┌dacă x%10<c atunci y←y*10+c │││altfel y←c*p+y ││└■ ││ p←p*10 │└■ └■ scrie y ``

Condiția de oprire x=0 devine condiție de continuare negată: cât timp x≠0.

Prelucrarea primei cifre se scoate înaintea buclei, fiindcă repetă intră în corp cel puțin o dată, iar o structură cu test inițial poate să nu intre deloc. Fără asta, pentru x=0 algoritmul n-ar mai fi echivalent: cel dat intră o dată, ia cifra 0 și o sare, pe când cât timp x≠0 n-ar face nimic.

Lanț neelementar: 1, 2, 4, 5, 6, 2

Muchiile există toate: [1,2], [2,4], [4,5], [5,6], [6,2]. Nodul 2 apare de două ori, deci lanțul nu e elementar — exact ce se cere.

Ciclu elementar: 1, 2, 6, 1

Muchiile [1,2], [2,6] și [6,1] sunt în liste, primul și ultimul nod coincid, iar între ele niciun nod nu se repetă: e un ciclu elementar de lungime 3.

Un lanț e *elementar* când nu repetă niciun nod; un ciclu e *elementar* când nu repetă niciun nod în afară de cel de plecare, care e și cel de sosire.

Răspunsul din barem: ELEMENT

Se pleacă de la ELITIST și se schimbă doar caracterele de pe pozițiile 2, 3, 4 și 5. Pozițiile pare primesc s[0], adică E; cele impare primesc s[1]+i/2, adică litera aflată la i/2 poziții după L.

Primele două litere și ultima nu sunt atinse de buclă, așa că șirul devine ELEMENT.

int putere(int n)
{
    int rezultat = 0, minim = 0;
    for (int d = 2; (long long) d * d <= n; d++)
        if (n % d == 0)
        {
            int e = 0;
            while (n % d == 0)
            {
                n = n / d;
                e++;
            }
            if (minim == 0 || e < minim)
            {
                minim = e;
                rezultat = d;
            }
        }
    if (n > 1 && (minim == 0 || 1 < minim))
        rezultat = n;
    return rezultat;
}

#include <iostream>
using namespace std;

int main()
{
    int n, a[21][21], k;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    cin >> k;
    int r = k - 1;
    int ultim = a[r][r - 1];
    for (int j = r - 1; j > 0; j--)
        a[r][j] = a[r][j - 1];
    a[r][0] = ultim;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << a[i][j];
            if (j < n - 1)
                cout << ' ';
        }
        cout << '\n';
    }
    return 0;
}

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

Laturile sunt numere din [1,10], deci există cel mult zece modele distincte, oricât de multe elemente grafice ar fi.

Citesc fișierul o singură dată și țin un vector frecv cu zece poziții, în care număr de câte ori apare fiecare latură. Nu păstrez șirul.

La final parcurg vectorul: pentru fiecare latură care apare măcar o dată adaug 10 lei — taxa de proiectare, plătită o singură dată pe model — plus latură · latură înmulțit cu numărul de elemente de acel fel.

Pe exemplul din enunț, 1 7 2 1 1 2 1 7 2: latura 1 apare de 4 ori, latura 2 de 3 ori, latura 7 de 2 ori. Total: (10 + 4·1) + (10 + 3·4) + (10 + 2·49) = 14 + 22 + 108 = 144.

De ce e eficient: fiecare număr e citit și numărat o singură dată, deci timpul e O(n) pentru cele cel mult 10⁶ numere, plus o trecere fixă prin cele zece poziții. Memoria e constantă — zece contoare — indiferent cât de lung e fișierul.

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

int main()
{
    ifstream f("bac.in");
    long long frecv[11] = {0};
    int x;
    while (f >> x)
        frecv[x]++;
    f.close();
    long long total = 0;
    for (int v = 1; v <= 10; v++)
        if (frecv[v] > 0)
            total = total + 10 + frecv[v] * v * v;
    cout << total;
    return 0;
}