Bac informatică 2020 Varianta 6, rezolvată

Răspuns corect: d) 7.5

Împărțirea 5.0/2 are un operand real, deci se face împărțire reală: rezultatul e 2.5, nu 2. De aici, 3+2.5+2 = 7.5, varianta d).

Dacă în locul lui 5.0 ar fi fost 5, amândoi operanzii ar fi fost întregi, 5/2 ar fi dat 2, iar expresia ar fi valorat 7. Punctul zecimal e singura diferență, și schimbă tot.

Răspuns corect: b) 0,2,0,1

Subprogramul coboară până la i=3 fără să afișeze nimic, iar afișările se fac la întoarcere:

Se afișează deci, în ordine: v[3]+1, v[2], v[1], v[0]. Ca să iasă 2020, trebuie ca v[3]+1=2, v[2]=0, v[1]=2, v[0]=0, adică tabloul 0, 2, 0, 1 — varianta b).

Atenție la v[3]: el e 1 în tablou, nu 2; abia după creșterea din subprogram devine 2.

Răspuns corect: c) (80,70,30,20)

Backtracking-ul încearcă sumele în ordine crescătoare pentru fiecare poziție, păstrând condiția ca fiecare să plătească strict mai puțin decât cel dinaintea lui, iar totalul să fie 200.

Primele patru coincid cu cele din enunț. După ele, cu primii doi 80, 60, mai există o singură împărțire a celor 60 de lei rămași: 50, 10. Apoi crește al doilea la 70, rămân 50 de lei pentru ultimii doi, iar prima împărțire validă, în ordine crescătoare pe poziția a treia, e 30, 20 — varianta c).

Varianta a) n-ar fi validă deloc: 45 și 15 nu se împart la 10.

Răspuns corect: c) 5

În vectorul de „tați”, un nod e frunză dacă nu apare ca tată al nimănui.

Nodurile care apar ca tați sunt 7, 5, 6, 3 și 8 — ele au cel puțin un fiu. Rămân 1, 2, 4, 9 și 10, care nu apar nicăieri în listă: sunt cele 5 frunze, varianta c).

Nodul 6 e rădăcina, fiindcă are tatăl 0, dar asta nu-l face frunză: are fiii 3 și 7.

Răspuns corect: a) 4

Din matricea de adiacență, muchiile sunt [1,2], [1,4], [1,5], [2,3], [3,4]: un pătrat 1-2-3-4-1 de care atârnă nodul 5, legat doar de 1.

Un graf parțial păstrează toate nodurile și alege o parte dintre muchii. Ca să rămână conex:

• muchia [1,5] trebuie păstrată, altfel nodul 5 rămâne izolat;
• din pătrat se poate scoate cel mult o muchie: scoțând una, rămâne un lanț care ține nodurile legate; scoțând două, pătratul se rupe.

Deci avem graful întreg, plus patru grafuri obținute scoțând pe rând câte una dintre cele patru muchii ale pătratului: 5 grafuri parțiale conexe cu totul. Cum se cer cele diferite de graful dat, rămân 4 — varianta a).

Răspunsul din barem: 1 1 1 0 0

Variabila c ia pe rând valorile 0, 2, 4, 6, 8 — crește din doi în doi și se oprește când trece de 9. Pentru fiecare dintre ele, bucla dinăuntru caută cifra c printre cifrele lui a, oprindu-se fie când s-au terminat cifrele, fie de îndată ce a găsit-o (x=1).

Numărul citit e 240107, cu cifrele 2, 4, 0, 1, 0, 7:

Deci 1 1 1 0 0. Cu alte cuvinte, algoritmul spune, pentru fiecare cifră pară, dacă apare sau nu în număr.

Răspunsul din barem: 102468 986420

Ca toate cele cinci valori afișate să fie nenule, numărul trebuie să conțină toate cifrele pare: 0, 2, 4, 6 și 8. Cum are șase cifre, toate distincte, mai rămâne loc pentru exact o cifră, care poate fi oricare dintre cele impare.

Cel mai mic: alegem cifra suplimentară cât mai mică, deci 1, și așezăm cifrele crescător. Numărul nu poate începe cu 0, așa că pe prima poziție vine 1, iar 0 imediat după: 102468.

Cel mai mare: alegem cifra suplimentară cât mai mare, deci 9, și așezăm cifrele descrescător: 986420.

#include <iostream>
using namespace std;

int main()
{
    int a, b, c = 0, x;
    cin >> a;
    do
    {
        b = a;
        x = 0;
        do
        {
            if (b % 10 == c)
                x = 1;
            b = b / 10;
        } while (b != 0 && x == 0);
        cout << x << ' ';
        c = c + 2;
    } while (c <= 9);
    return 0;
}

`` citește a (număr natural) c←0 ┌repetă │ b←a; x←0 │┌dacă b%10=c atunci ││ x←1 │└■ │ b←[b/10] │┌cât timp b≠0 și x=0 execută ││┌dacă b%10=c atunci │││ x←1 ││└■ ││ b←[b/10] │└■ │ scrie x,' ' │ c←c+2 └până când c>9 ``

A doua structură repetă are condiția de oprire b=0 sau x=1, deci se repetă cât timp b≠0 și x=0 — condiția negată.

Dar repetă execută corpul cel puțin o dată, iar cât timp poate să nu-l execute deloc. De aceea prima verificare a fost scoasă înaintea buclei. Fără ea, algoritmul n-ar mai fi echivalent pentru a=0: cel dat verifică o dată cifra 0 și afișează 1 pentru c=0, pe când un simplu cât timp b≠0 n-ar intra niciodată în corp și ar afișa 0.

```cpp struct capacitate { int interna; int externa; };

struct calculator
{
    char monitor;
    capacitate memorie;
};

calculator c; ```

Expresia c.memorie.interna are două puncte, deci cere o structură în altă structură: c are un câmp memorie, iar acela are câmpurile interna și externa.

Tipurile vin din enunț: monitorul e o literă, deci char; capacitățile sunt numere naturale până la 10⁶, deci int. Eticheta structurii mari trebuie să fie calculator, cum cere cerința; structura dinăuntru poate purta orice nume, important e ca membrul din calculator să se cheme memorie.

``cpp for (i = 0; i < 9; i++) for (j = 0; j < 9; j++) if (j >= 9 - i && j <= i - 1) a[i][j] = '<'; else a[i][j] = '>'; ``

Semnele < formează un triunghi care pornește dintr-un singur element, pe linia 5, coloana 4, și se lărgește cu câte o poziție în fiecare parte pe fiecare linie de mai jos.

Pe linia i, triunghiul se întinde de la coloana 9-i până la coloana i-1:

Pentru liniile de sus intervalul iese gol de la sine — pe linia 4, de pildă, ar merge „de la 5 până la 3”, ceea ce nu cuprinde nimic — deci nu mai e nevoie de nicio verificare în plus pentru ele. În rest se pune >.

int suma(int a, int b)
{
    int s = 0;
    for (int d = 1; d <= a && d <= b; d++)
        if (a % d == 0 && b % d == 0)
            s = s + d;
    return s;
}

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

int main()
{
    char s[101], cuv[51][101];
    cin.getline(s, 101);
    int k = 0;
    for (char *p = strtok(s, " "); p != NULL; p = strtok(NULL, " "))
    {
        strcpy(cuv[k], p);
        k++;
    }
    int rotite = 0;
    for (int i = 0; i < k; i++)
    {
        int n = strlen(cuv[i]);
        if (n >= 3)
        {
            char prima = cuv[i][0];
            for (int j = 0; j < n - 1; j++)
                cuv[i][j] = cuv[i][j + 1];
            cuv[i][n - 1] = prima;
            rotite++;
        }
    }
    if (rotite == 0)
    {
        cout << "nu exista";
        return 0;
    }
    for (int i = 0; i < k; i++)
    {
        cout << cuv[i];
        if (i < k - 1)
            cout << ' ';
    }
    return 0;
}

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

Într-un șir palindromic, fiecare termen are perechea lui la aceeași distanță de celălalt capăt. Deci fiecare valoare trebuie să apară de un număr par de ori — cu o singură excepție: dacă șirul are lungime impară, valoarea din mijloc n-are pereche.

Algoritmul: citesc șirul o singură dată și țin un vector frecv cu 1000 de poziții, în care număr de câte ori apare fiecare valoare. La final număr câte valori au apărut de un număr impar de ori: dacă sunt cel mult una, răspunsul e DA, altfel NU.

Pe exemplul din enunț — 100 30 100 30 500 30 30 — valoarea 100 apare de două ori, 30 de patru ori, iar 500 o singură dată: o singură frecvență impară, deci DA (de pildă 30 100 30 500 30 100 30).

De ce e eficient: fiecare număr e citit și numărat o singură dată, deci timpul e O(n), iar la final se mai face o trecere prin cele 1000 de poziții, care nu depinde de lungimea șirului. Memoria e constantă: vectorul de frecvențe are mereu 1000 de poziții, fiindcă atâtea valori se pot afla în șir, oricât de lung ar fi el — șirul însuși nu se păstrează niciodată.

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

int main()
{
    ifstream f("bac.in");
    int frecv[1001] = {0}, x;
    while (f >> x)
        frecv[x]++;
    f.close();
    int impare = 0;
    for (int v = 1; v <= 1000; v++)
        if (frecv[v] % 2 == 1)
            impare++;
    if (impare <= 1)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}