Bac informatică 2020 Varianta 2, rezolvată

Răspuns corect: a) 0

Cum x ia valori de la 1000 la 2000, x-999 ia valori de la 1 la 1001.

Restul împărțirii la 1000 al acestor numere este:

• 1…999 → chiar ele, deci de la 1 la 999
• 1000 → 0
• 1001 → 1

Valoarea minimă este deci 0, obținută pentru x=1999. Varianta d) nici n-ar fi posibilă: un rest la împărțirea cu 1000 nu poate fi 1000.

Răspuns corect: d) 0071249

Subprogramul afișează x după apelul recursiv, deci numerele ies în ordine inversă față de coborâre, iar zerourile ies la coborâre:

Citite în ordinea execuției: 0, 0, 7, 1, 2, 4, 9 — adică 0071249, varianta d).

Capcana e că cout<<x nu e în else: se execută la fiecare apel, și la cele care au recursivitate, și la cel care oprește coborârea.

Răspuns corect: a) (aperitiv, salată, paste, desert)

Felurile se iau în ordinea din mulțime: 1 aperitiv, 2 desert, 3 legume, 4 paste, 5 salată, 6 supă. Se generează aranjamente de câte patru (ordinea contează), în ordine crescătoare a indicilor, iar cele care încalcă o condiție se resping:

Primele cinci coincid cu cele date în enunț, ceea ce confirmă ordinea. Al șaselea este a).

Răspuns corect: b) 2

Din desen, arcele sunt: 1→2, 2→5, 5→1, 5→3, 5→4, 3→4, 4→3.

Două vârfuri sunt în aceeași componentă tare conexă dacă se poate ajunge de la unul la altul în amândouă sensurile.

• 1, 2 și 5 formează un circuit: 1→2→5→1. Deci sunt împreună.
• 3 și 4 sunt legate în amândouă sensurile: 3→4 și 4→3. Deci sunt împreună.

Din 5 se ajunge la 3 și la 4, dar înapoi nu: nu există niciun arc care să iasă din {3,4} spre restul grafului. Deci cele două grupuri nu se pot uni.

Sunt 2 componente tare conexe: {1,2,5} și {3,4} — varianta b).

Răspuns corect: c) 10

Arborele are 20 de noduri, dintre care 10 sunt frunze, deci 10 noduri au cel puțin un fiu.

Ca să aibă un nod cât mai mulți fii, restul nodurilor interne trebuie „consumate” cât mai economic: le înșiri într-un lanț — rădăcina cu un fiu, acela cu un fiu, și tot așa, nouă noduri interne. Al zecelea nod intern, cel din capătul lanțului, primește drept fii toate cele 10 frunze.

Mai mult de 10 nu se poate: un nod cu 11 fii ar avea printre ei cel puțin un nod intern, iar acela ar avea nevoie de un fiu propriu — care ar trebui să fie tot o frunză, și n-au mai rămas. Răspunsul este c).

Răspunsul din barem: 2020

Bucla cât timp taie ultima cifră a lui x atât timp cât aceasta e mai mare decât cifra dinaintea ei. Ce rămâne se adună la m.

Suma este 0+20+100+0+1900 = 2020, iar cum m>0, se afișează 2020.

De reținut: un număr cu o singură cifră se reduce mereu la 0, fiindcă „cifra dinaintea ei” e 0.

1234 5678

Ca să se afișeze niciunul, suma m trebuie să fie 0, iar cum toate numerele citite sunt naturale, fiecare dintre ele trebuie să se reducă la 0.

Un număr se reduce la 0 doar dacă bucla îi taie toate cifrele, adică dacă la fiecare pas ultima cifră e mai mare decât cea dinaintea ei. Asta înseamnă un număr cu cifrele strict crescătoare.

1234: 4>3 → 123, 3>2 → 12, 2>1 → 1, 1>0 → 0. La fel 5678. Amândouă sunt în intervalul cerut și sunt distincte, deci se afișează niciunul.

Orice altă pereche cu cifre strict crescătoare merge la fel de bine: 1259 și 3456, de exemplu.

#include <iostream>
using namespace std;

int main()
{
    int n, m = 0, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        while (x % 10 > x / 10 % 10)
            x = x / 10;
        m = m + x;
    }
    if (m > 0)
        cout << m;
    else
        cout << "niciunul";
    return 0;
}

`` citește n (număr natural nenul) m←0 i←1 ┌cât timp i≤n execută │ citește x (număr natural) │┌cât timp x%10 > [x/10]%10 execută ││ x←[x/10] │└■ │ m←m+x │ i←i+1 └■ ┌dacă m>0 atunci scrie m │altfel scrie "niciunul" └■ ``

pentru i←1,n face singur trei lucruri: pornește contorul de la 1, verifică dacă a depășit n și îl crește la fiecare pas. Cu cât timp trebuie scrise toate trei separat: inițializarea înainte de buclă, condiția i≤n în capul ei și creșterea i←i+1 ca ultimă instrucțiune din corp.

Dacă ai uita i←i+1, bucla n-ar mai avea cum să se oprească.

```cpp struct punct { double x; double y; };

struct figura
{
    punct centru;
    double raza;
};

figura c; ```

Expresiile din enunț cer două niveluri: c.centru.x înseamnă că c are un câmp centru, iar acela are la rândul lui câmpurile x și y. Deci e nevoie de o structură în altă structură.

Coordonatele și raza sunt numere reale, deci câmpurile sunt double (merge și float). Numele lor nu sunt la alegere: centru, x, y și raza sunt impuse de expresiile date, iar eticheta structurii mari trebuie să fie figura, cum cere enunțul.

``cpp for (i = 0; i < 7; i++) for (j = 0; j < 7; j++) if (j < i) m[i][j] = '+'; else m[i][j] = 'a' + j - i; ``

Privește tabloul cerut pe diagonală: pe diagonala principală, unde i=j, stă peste tot litera a. Deasupra ei literele merg mai departe — b, c, d — iar sub ea sunt doar +.

Asta dă regula:

• dacă j<i (sub diagonală) → '+'
• altfel → litera aflată la j-i poziții după a, adică 'a'+j-i

În C/C++ un caracter e un număr, deci 'a'+j-i e chiar litera dorită: pentru i=0, j=6 iese 'a'+6, adică 'g'.

int multiplu(int n)
{
    for (int k = 1; ; k++)
    {
        int v = n * k;
        int r = (int) sqrt((double) v);
        while (r * r > v)
            r--;
        while ((r + 1) * (r + 1) <= v)
            r++;
        if (r * r == v)
            return v;
    }
}

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

int main()
{
    char s[101];
    cin.getline(s, 101);
    int inauntru = 0;
    for (int i = 0; s[i] != '\0'; i++)
    {
        if (s[i] == '<')
            inauntru = 1;
        else if (s[i] == '>')
            inauntru = 0;
        else if (inauntru == 1 && s[i] >= 'a' && s[i] <= 'z')
            s[i] = s[i] - 'a' + 'A';
    }
    cout << s;
    return 0;
}

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

Se citește șirul o singură dată, din fișier, fără să fie păstrat.

La orice moment țin minte doar trei valori consecutive: a, b și c. Dacă b>a și b>c, atunci b este vârf, iar diferența dintre vecinii lui este |a-c|.

Păstrez două valori: cea mai mică diferență găsită până acum și vârful care a dat-o. Un vârf nou îl înlocuiește pe cel păstrat dacă are diferența mai mică sau dacă are aceeași diferență, dar e mai mare — exact regula din enunț. Dacă la final n-am găsit niciun vârf, afișez nu exista.

După fiecare pas, „fereastra” se mută cu o poziție: a ia valoarea lui b, b pe a lui c, iar c devine numărul următor din fișier.

De ce e eficient: fiecare număr e citit și comparat o singură dată, deci timpul e O(n). Memoria e O(1): oricât de lung ar fi șirul — și poate avea 10⁶ numere — se rețin doar cele trei valori din fereastră și cele două valori ale răspunsului, niciodată șirul întreg.

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

int main()
{
    ifstream f("bac.in");
    long long a, b, c, difMin = -1, varf = -1;
    if (!(f >> a) || !(f >> b))
    {
        cout << "nu exista";
        return 0;
    }
    while (f >> c)
    {
        if (b > a && b > c)
        {
            long long dif = llabs(a - c);
            if (difMin < 0 || dif < difMin || (dif == difMin && b > varf))
            {
                difMin = dif;
                varf = b;
            }
        }
        a = b;
        b = c;
    }
    f.close();
    if (difMin < 0)
        cout << "nu exista";
    else
        cout << varf;
    return 0;
}