Bac informatică 2022 Simulare, rezolvată

Răspuns corect: d) !(x>3) || !(x<=30)

!(x>3) înseamnă x<=3, iar !(x<=30) înseamnă x>30, deci d) este chiar expresia dată. În a) rămâne x>=3 && x<30; în b) rămâne x<3 || x>30, care e 0 pentru x=3, deși expresia dată e 1; în c) rămâne x>30, care pierde toate valorile mai mici sau egale cu 3.

Răspuns corect: b) 3

Subprogramul împarte intervalul în două jumătăți, până ajunge la câte un singur element, și adună câte 1 pentru fiecare poziție pe care valoarea coincide cu indicele. În tabloul (7,1,2,5,4) sunt trei astfel de poziții: v[1]=1, v[2]=2 și v[4]=4, deci rezultatul este 3.

Răspuns corect: c) {Valentin, Alin, Răzvan, Ștefan}

Echipele se formează pe roluri, în ordinea jucătorilor din mulțime. După {Cristian, Valentin, Ștefan, Răzvan} s-au epuizat toate echipele cu liderul Cristian, deci se trece la următorul jucător care poate fi lider — Valentin — iar ca secund se ia primul posibil, Alin; pentru ultimele două roluri, prima variantă este Răzvan, apoi Ștefan.

Răspuns corect: a) oras[0].nrLocuitori/oras[0].suprafata

oras este un tablou de înregistrări, deci se alege întâi elementul — oras[0] — și abia apoi câmpul: oras[0].nrLocuitori și oras[0].suprafata. Celelalte trei variante inversează ordinea, punând indicele sau numele tabloului după câmp, ceea ce nu are sens.

Răspuns corect: c) 2

Un subgraf se obține ștergând noduri, împreună cu muchiile care pleacă din ele; muchiile rămase între nodurile păstrate rămân toate. Din graful complet cu 4 noduri se obțin astfel grafuri complete cu 4, 3, 2, 1 sau 0 noduri, adică 6, 3, 1, 0 și 0 muchii. Valoarea 2 nu poate fi obținută.

Răspunsul din barem: 3

Pentru fiecare număr citit se taie cifre de la dreapta cât timp numărul rămas are altă paritate decât x, iar la final se compară cu x. Cum x=16 este par: 4273 ajunge 42, diferit de 16; 1679 ajunge 16 și se numără; 3165 ajunge 316, diferit; 16 este deja par și se numără; 200 e par de la început, dar nu e 16; 167 ajunge 16 și se numără. În total, trei numere.

2213 și 2235

x este 22, deci par: dintr-un număr se taie cifre cât timp ce rămâne este impar. Ca un număr de patru cifre să ajungă la 22, el trebuie să înceapă cu 22, iar ultimele două cifre trebuie să fie impare — altfel tăierea s-ar opri mai devreme, pe un număr par diferit de 22. Cum n este 2, se scriu exact două numere de forma 22xy cu x și y cifre impare, de exemplu 2213 și 2235.

#include <iostream>
using namespace std;

int main()
{
    int n, x, y, nr = 0, i = 1;
    cin >> n >> x;
    while (i <= n)
    {
        cin >> y;
        while (y != 0 && y % 2 != x % 2)
            y = y / 10;
        if (y == x) nr = nr + 1;
        i = i + 1;
    }
    cout << nr;
    return 0;
}

citește n,x (numere naturale nenule)
 nr←0
┌pentru i←1,n execută
│ citește y (număr natural)
│┌cât timp y≠0 și y%2≠x%2 execută
││ y←[y/10]
│└■
│┌dacă y=x atunci nr←nr+1
│└■
└■
 scrie nr

Structura pentru ține singură contorul: îl pornește de la 1, îl compară cu n și îl crește la fiecare pas. De aceea i←1 dinaintea buclei și i←i+1 din corpul ei dispar, iar restul algoritmului rămâne neschimbat.

1, 3 și 4

Rădăcina este nodul 5, fiindcă are tatăl 0. Fiii lui sunt 2, 3 și 9, deci ei sunt pe nivelul 1; pe nivelul 2 se află 8 și 10 (fiii lui 2) și 7 (fiul lui 9); pe nivelul 3 se află 1, 4 și 6, fiii lui 10. Frunzele — nodurile care nu apar în vectorul de „tați" — sunt 3, 8, 7, 1, 4 și 6, iar dintre ele pe niveluri impare stau 3 (nivelul 1) și 1, 4, 6 (nivelul 3). Oricare trei dintre acestea sunt un răspuns bun.

ok = 0;
for (j = 1; j < 14; j++)
    if (a[0][j] == a[1][j - 1] && a[1][j - 1] == a[1][j + 1] && a[1][j + 1] == a[2][j])
        ok = 1;

Un romb are în mijloc vasul de pe linia 1, iar cele patru flori din jurul lui sunt deasupra — a[0][j] —, dedesubt — a[2][j] — și în stânga și în dreapta, pe aceeași linie: a[1][j-1] și a[1][j+1]. Toate patru trebuie să fie de același fel. Coloana centrului merge de la 1 la 13, ca vecinii din stânga și din dreapta să existe. La prima potrivire ok devine 1 și rămâne așa.

void rest(int x, int y, int n, int &k)
{
    for (k = n; k >= 1; k--)
        if (k % x == 2 && k % y == 2) return;
    k = 0;
}

Se cere cea mai mare valoare potrivită, deci căutarea pornește de la n și coboară: primul număr găsit este chiar răspunsul, iar subprogramul se oprește acolo. Dacă bucla se termină fără să găsească ceva, k rămâne 0, adică exact valoarea cerută în acest caz. Parametrul k e transmis prin referință, fiindcă prin el se furnizează rezultatul.

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

char s[251], x[251];

int main()
{
    cin.getline(s, 251);
    cin >> x;
    int gasit = 0;
    for (char *p = strtok(s, ";"); p != NULL; p = strtok(NULL, ";"))
    {
        while (*p == ' ') p++;              // spațiul de după punct și virgulă
        char *sp = strchr(p, ' ');
        if (sp == NULL) continue;
        *sp = '\0';                        // p rămâne prenumele, sp+1 este numele
        if (strcmp(p, x) == 0)
        {
            if (gasit) cout << ' ';
            cout << sp + 1;
            gasit = 1;
        }
    }
    if (gasit == 0) cout << "NU";
    return 0;
}

Lista se taie în invitați după ;, iar fiecare invitat se taie la primul spațiu: în stânga rămâne prenumele, în dreapta numele. Prenumele se compară cu x, iar numele celor care se potrivesc se scriu unul după altul, separate prin câte un spațiu. Dacă nu s-a scris nimic până la sfârșit, se afișează NU.

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

45 = 3²·5, deci 45^{^p} înseamnă 3^{^2p}·5^{^p}. Numărul p căutat este cel mai mare pentru care produsul 1·2·…·n se împarte la 3^{^2p} și la 5^{^p}, adică p este cea mai mică dintre valorile [e₃/2] și e₅, unde e₃ și e₅ sunt puterile lui 3, respectiv ale lui 5, din descompunerea produsului.

Puterea unui număr prim d în produsul 1·2·…·n se obține fără a calcula produsul: dintre numerele de la 1 la n, [n/d] se împart la d, [n/d²] se împart încă o dată la d și așa mai departe, deci e_d = [n/d] + [n/d²] + [n/d³] + … Suma are termeni doar cât timp puterea lui d nu depășește n.

Numărul de termeni este deci logaritmic în raport cu n — pentru n de ordinul unui miliard, sub douăzeci de împărțiri pentru fiecare dintre cele două numere prime — iar memoria folosită este constantă: doar câteva variabile. Produsul propriu-zis nu se calculează niciodată, fiindcă ar depăși orice tip de date.

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

// Puterea numărului prim d în produsul 1·2·…·n.
long long putere(long long n, long long d)
{
    long long e = 0, p = d;
    while (p <= n)
    {
        e = e + n / p;
        if (p > n / d) break;   // altfel p*d ar depăși domeniul
        p = p * d;
    }
    return e;
}

int main()
{
    long long n;
    cin >> n;
    long long e3 = putere(n, 3) / 2, e5 = putere(n, 5);
    long long p = e3 < e5 ? e3 : e5;
    ofstream g("bac.txt");
    g << p;
    g.close();
    return 0;
}