[canonical]: https://grile.online/informatica/combinatorica

> Pagina completă: https://grile.online/informatica/combinatorica
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Grile Combinatorică · Informatică

1 grilă, în 1 set, cu explicații.

## Teaser gratuit, fără cont

1. La o masă rotundă sunt $3$ copii ($c_1, c_2, c_3$) și $4$ adulți ($a_1, a_2, a_3, a_4$). În câte moduri pot fi așezate persoanele astfel încât cei $3$ copii să nu fie toți alăturați? Maxim $2$ copii pot sta consecutiv. Locurile nu sunt numerotate.

a) $120$
b) $35$
c) $5$
d) $576$
e) $840$
f) $90$

Răspuns corect: d) $576$

Numărul total de așezări circulare ale celor $7$ persoane este $(7-1)! = 720$; tratând cei $3$ copii ca un bloc unic, rezultă $(5-1)! \cdot 3! = 144$ așezări cu toți cei $3$ alăturați, deci $720-144=576$ rămân valide.

2. Fie $a$ și $b$ două valori întregi, cu $a \le b$, și $v$ un vector sortat descrescător cu $n$ elemente (numere întregi). Dorim să determinăm numărul de elemente din $v$ care sunt în intervalul $[a,b]$. Care este complexitatea temporală a algoritmului optim?

a) $O(\log^2 n)$
b) $O(n \log n)$
c) $O(1)$
d) $O(\log n)$
e) $O(n)$
f) $O(n^2)$

Răspuns corect: d) $O(\log n)$

Vectorul fiind sortat, marginile intervalului $[a,b]$ se pot localiza prin două căutări binare (una pentru fiecare capăt), iar numărul de elemente din interval rezultă direct din diferența pozițiilor găsite — complexitate $O(\log n)$.

(din capitolul Complexitate)

3. O matrice rară (cu multe elemente nule) este reprezentată prin dimensiunile ei: numărul de linii și numărul de coloane (`nl` și `nc`), numărul de elemente nenule (`nn`) și un vector `term` care conține maxim $100$ de termeni nenuli caracterizați prin poziție (`lin`, `col`) și valoare (`val`).

Matricea: $$A = \begin{pmatrix} 0 & 0 & 0 & 0 & 7 \\ 2 & 0 & 0 & 1 & 0 \\ 0 & 3 & 0 & 0 & 1 \\ 0 & 4 & 0 & 0 & 9 \end{pmatrix}$$ se va reprezenta (în ordinea parcurgerii pe linii, de la stânga la dreapta) folosind variabila `mr`.

Ce va afișa secvența `printf("%d", mr.term[1].val);` (Pascal: `Write(mr.term[2].val);`)?

a) $4$
b) $3$
c) $1$
d) $2$
e) $5$
f) $7$

Răspuns corect: d) $2$

Parcurgând matricea pe linii, primii doi termeni nenuli sunt $7$ (linia $0$, coloana $4$) și $2$ (linia $1$, coloana $0$); `mr.term[1]` este al doilea termen din vector (indexare de la $0$ în C), deci `mr.term[1].val` $=2$ — aceeași valoare pe care Pascal o accesează prin `mr.term[2]` (indexare de la $1$).

(din capitolul Structuri de date)

4. Se definește $\mathrm{ARB}(n)$ un arbore binar în care: toate nodurile au $0$ sau $2$ copii; toate frunzele sunt pe același nivel; numărul de niveluri este $n$. Rădăcina este pe nivelul $1$ și are valoarea $1$. Un nod cu valoarea $x$ (care nu este frunză) are: copilul stâng $2x$; copilul drept $2x+1$.

Exemplu: $\mathrm{ARB}(3)$ conține $7$ noduri, iar $\mathrm{sum}(\mathrm{ARB}(3)) = 103$. Cât este $\mathrm{sum}(\mathrm{ARB}(5)) - \mathrm{sum}(\mathrm{ARB}(4))$?

a) $3072$
b) $2987$
c) $2869$
d) $3061$
e) $2976$
f) $3125$

Răspuns corect: b) $2987$

Construind $\mathrm{ARB}(n)$ conform regulii date, suma valorilor tuturor nodurilor de pe un nivel nou adăugat este determinată exact de acea regulă; enunțul indică $\mathrm{sum}(\mathrm{ARB}(3))=103$, iar $2987 = 29 \times 103$ este singura variantă divizibilă cu acest număr.

(din capitolul Arbori binari)

5. Care dintre următoarele expresii verifică proprietatea $|x-a| < b$ pentru $a, b, x$ întregi?

a) `I3`
b) `I2` și `I5`
c) `I4`
d) `I1`
e) `I2` și `I5`
f) `I5`

Răspuns corect: d) `I1`

`I1` (`a-b < x && x < a+b`) implementează corect conjuncția $a-b < x$ și $x < a+b$, echivalentă cu $|x-a| < b$. Celelalte fie folosesc `||` în loc de `&&` (`I2`), inversează inegalitățile (`I3`), înlănțuie incorect operatorii de comparație (`I4`), fie testează o singură margine (`I5`).

(din capitolul Expresii)

## Seturi care conțin acest capitol

- [Informatică #003](https://grile.online/informatica/rezolva?set=informatica-poli-2025)