Bac informatică 2024 Varianta 3, rezolvată

Răspuns corect: a) x%2==0 && (y+1)%2!=0

Un număr este par când restul împărțirii lui la 2 este 0. x%2==0 spune că x este par, iar (y+1)%2!=0 spune că y+1 este impar, adică y este par. Legate cu &&, cele două cer ca ambele numere să fie pare: varianta a).

b), c) și d) sunt adevărate ori de câte ori x și y au aceeași paritate, deci și când amândouă sunt impare (de exemplu 1 și 3).

Răspuns corect: d) 23022100

Pentru x≥10, f(x,y) îl apelează întâi pe f(x/10,y+1) și abia apoi afișează ultima cifră a lui x; la sfârșit, în orice caz, afișează y.

f(2,3) afișează 2, apoi 3. Revenind, f(20,2) afișează 0 și 2, f(202,1) afișează 2 și 1, iar f(2020,0) afișează 0 și 0. În ordine: 23022100.

Răspuns corect: c) (2,6,4,1,3,5)

Permutările se generează în ordine lexicografică. Primele șase au prefixul (2,4,6) și cuprind toate ordinile valorilor impare pe ultimele trei poziții, iar (2,4,6,5,3,1) este ultima dintre ele.

Urmează cel mai mic prefix cu trei valori pare de după (2,4,6): (2,6,4), completat cu cea mai mică ordine a valorilor impare, (1,3,5): (2,6,4,1,3,5). a) și b) încep cu 4, deci vin mai târziu, iar d) conține de două ori valoarea 2.

Răspuns corect: d) x[10].tip

x este un tablou de structuri, iar al 11-lea sortiment este x[10], fiindcă numerotarea începe de la 0. Tipul lui este câmpul tip: x[10].tip.

a) și c) folosesc numele tipului, ciocolata, ca și cum ar fi un câmp, iar b) îl tratează pe tip ca pe un tablou.

Răspuns corect: b) 15

Suma gradelor tuturor nodurilor este dublul numărului de muchii, 20. Ca graful să aibă cât mai multe noduri, fiecare nod trebuie să consume cât mai puțin din această sumă: nodurile cu grad impar câte 1, iar cele cu grad par nenul câte 2.

Cele șase noduri de grad impar folosesc 6, iar cei 14 rămași ajung pentru 7 noduri de grad 2. Cu cele două noduri izolate, graful are 2 + 6 + 7 = 15 noduri. Un astfel de graf există: cele 7 noduri de grad 2 formează un ciclu (7 muchii), iar cele 6 de grad 1 sunt legate două câte două (3 muchii).

Răspunsul din barem: 9

9

Fiecare număr citit se împarte la 3 (cu partea întreagă) până ajunge la cel mult 3, iar valoarea rămasă, dacă nu e 0, se înmulțește în p.
15 → 5 → 1; 27 → 9 → 3; 10 → 3; 1 → 0 (nu se înmulțește); 17 → 5 → 1. Produsul este 1 · 3 · 3 · 1 = 9.

Exemplu: 6 20

Pentru n=2 se citesc două numere, iar produsul valorilor rămase trebuie să fie 4. Valoarea rămasă este cel mult 3, deci singura posibilitate este ca ambele numere să se reducă la 2.
Un număr se reduce la 2 dacă, după împărțiri repetate la 3, ajunge în intervalul [6,8] (care dă 2), adică dacă aparține unui interval de forma [2·3^k, 3^(k+1)), cu k ≥ 1: [6,8], [18,26], [54,80], [162,242], [486,728].

#include <iostream>
using namespace std;

int main()
{
    int n, p = 1, i, x;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> x;
        do
        {
            x = x / 3;
        } while (x > 3);
        if (x != 0) p = p * x;
    }
    cout << p;
    return 0;
}

pentru i←1,n execută devine for (i = 1; i <= n; i++). repetă…până când x≤3 devine do…while cu condiția negată, x > 3, iar [x/3] este împărțirea întreagă din C/C++.

citește n (număr natural nenul)
p←1
i←1
┌cât timp i≤n execută
│ citește x (număr natural)
│┌repetă
││ x←[x/3]
│└până când x≤3
│┌dacă x≠0 atunci
││ p←p*x
│└■
│ i←i+1
└■
scrie p

Cu cât timp, contorul se gestionează explicit: i primește valoarea inițială 1 înainte de buclă, se continuă cât timp i≤n, iar i←i+1 se face la sfârșitul corpului.

Răspunsul din barem: 2,3,1,7

2,3,1,7

Rădăcina este nodul 2, singurul cu tatăl 0. Fiii fiecărui nod: 2 are fiii 3 și 5, 3 are fiul 1, 1 are fiul 7, iar 5 are fiii 4, 6 și 8.
Cel mai lung lanț care pornește din rădăcină coboară până la cea mai adâncă frunză: 2, 3, 1, 7 are lungimea 3, iar lanțurile prin 5 (de exemplu 2, 5, 4) au lungimea 2.

for(i=0;i<9;i++)
  for(j=0;j<9;j++)
    if(i+j<=3 || i+j>=13) a[i][j]=4;
    else a[i][j]=2;

Pe fiecare diagonală paralelă cu cea secundară suma indicilor i+j este constantă. Valorile 4 ocupă colțul din stânga-sus, unde i+j ≤ 3, și colțul din dreapta-jos, unde i+j ≥ 13; toate celelalte elemente sunt 2. Sunt două atribuiri, sub limita de patru.

int majImp(int a, int b)
{
    int n, d, si, sp;
    for (n = a; n <= b; n++)
    {
        si = 0;
        sp = 0;
        for (d = 2; d <= n / 2; d++)
            if (n % d == 0)
            {
                if (d % 2 == 1) si = si + d;
                else sp = sp + d;
            }
        if (si > sp) return n;
    }
    return 0;
}

Numerele din interval se verifică în ordine crescătoare, deci primul număr major impar găsit este și cel mai mic, și se returnează imediat. Pentru fiecare n se adună separat divizorii proprii impari (si) și pari (sp); un divizor propriu este cel mult n/2, de aceea d merge până acolo.
Dacă niciun număr nu are proprietatea, bucla se termină și se returnează 0.

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

int main()
{
    char s[101], *p;
    int lung = -1, ok = 1;
    cin.getline(s, 101);
    p = strtok(s, " ");
    while (p != NULL)
    {
        if (lung == -1) lung = strlen(p);
        else if ((int)strlen(p) != lung) ok = 0;
        p = strtok(NULL, " ");
    }
    if (ok == 1) cout << "DA " << lung;
    else cout << "NU";
    return 0;
}

Textul se desparte în cuvinte cu strtok. Lungimea primului cuvânt se reține în lung, iar fiecare cuvânt următor se compară cu ea; dacă unul are altă lungime, ok devine 0. La final se afișează DA și lungimea comună sau NU.

Cotele se citesc pe rând, fără să fie memorate. Se păstrează ultima cotă citită, lungimea scării curente (numărul de marcaje consecutive cu cote consecutive, terminată în cota curentă), precum și lungimea celei mai lungi scări găsite și ultima ei cotă.

Pentru fiecare cotă x: dacă x este cu 1 mai mare decât cota anterioară, scara curentă crește cu un marcaj; altfel începe o scară nouă, de lungime 1. Dacă scara curentă devine mai lungă decât cea mai lungă găsită, se rețin lungimea ei și cota x. La final, dacă cea mai lungă scară are mai puțin de 2 marcaje, se afișează nu exista; altfel cotele ei sunt numerele consecutive care se termină în ultima cotă reținută, deci se pot afișa fără să fi fost memorate.

Eficiență: fiecare cotă se prelucrează o singură dată, în timp constant, deci algoritmul este liniar în numărul de valori din fișier. Se folosesc doar câteva variabile simple, fără tablou, deci memoria este constantă.

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

int main()
{
    ifstream fin("bac.txt");
    int x, ult = -1, lg = 0, lgMax = 0, ultMax = 0, i;
    while (fin >> x)
    {
        if (x == ult + 1) lg++;
        else lg = 1;
        ult = x;
        if (lg > lgMax)
        {
            lgMax = lg;
            ultMax = x;
        }
    }
    fin.close();
    if (lgMax < 2) cout << "nu exista";
    else
        for (i = ultMax - lgMax + 1; i <= ultMax; i++)
            cout << i << ' ';
    return 0;
}

Programul face pașii de la 3.a. ult pornește de la -1, astfel încât prima cotă (cel puțin 10) începe sigur o scară nouă. Cotele scării maxime se reconstruiesc din ultima ei cotă și din lungime.