[canonical]: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-062

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-062
> 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 Model admitere MateInfo UB · Informatică #062

10 grile din Combinatorică, Programare dinamică, Backtracking, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul admitere MateInfo UB

## Teaser gratuit, fără cont

1. În câte moduri se pot alege un președinte și un vicepreședinte dintr-un grup de $7$ elevi?

a) $21$
b) $49$
c) $14$
d) $5040$
e) $42$
f) $7$

Răspuns corect: e) $42$

Ordinea contează (funcțiile sunt diferite): $A_7^2=7\cdot6=42$.

2. Care este scrierea în baza $3$ a numărului $100$?

a) $10210$
b) $10202$
c) $2201$
d) $11201$
e) $10201$
f) $1100100$

Răspuns corect: e) $10201$

$100=81+2\cdot9+1=1\cdot3^4+0\cdot3^3+2\cdot3^2+0\cdot3+1$, deci $10201_{(3)}$.

3. Un graf neorientat cu $10$ noduri are muchiile $[1,2]$, $[2,3]$, $[4,5]$, $[6,7]$, $[7,8]$, $[6,8]$. Care este numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex?

a) $5$
b) $4$
c) $3$
d) $2$
e) $9$
f) $6$

Răspuns corect: b) $4$

Componentele conexe sunt $\{1,2,3\}$, $\{4,5\}$, $\{6,7,8\}$, $\{9\}$, $\{10\}$ — în total $5$. Pentru a le lega sunt necesare cel puțin $5-1=4$ muchii.

4. Triunghiul de numere de mai jos se parcurge de la vârf spre bază; din fiecare număr se coboară fie direct dedesubt, fie dedesubt la dreapta.

$$\begin{matrix}4\\2\quad 4\\8\quad 3\quad 2\\6\quad 1\quad 2\quad 1\\3\quad 9\quad 2\quad 6\quad 1\end{matrix}$$

Care este suma maximă a numerelor de pe un drum?

a) $27$
b) $19$
c) $30$
d) $28$
e) $29$
f) $26$

Răspuns corect: e) $29$

Se calculează de jos în sus $S_{i,j}=a_{i,j}+\max(S_{i+1,j},S_{i+1,j+1})$. Drumul optim este $4\to2\to8\to6\to9$, cu suma $29$. Alegerea la fiecare pas a vecinului mai mare ($4\to4\to3\to2\to6$) dă doar $19$.

5. Care este numărul minim de pătrate perfecte nenule (se pot repeta) a căror sumă este $43$?

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

Răspuns corect: d) $3$

Cu $d_s=1+\min_{k^2\le s} d_{s-k^2}$ se obține $d_{43}=3$: $43=25+9+9$. Alegerea greedy a celui mai mare pătrat ($36+4+1+1+1$) folosește $5$, iar două pătrate nu ajung, deoarece $43$ dă restul $3$ la împărțirea cu $4$.