Pre-admitere Informatică 2024 — 20 aprilie — Varianta C

Se dă o matrice cu 3 linii și 3 coloane. Pornim din celula de start (1,1) și vrem să ajungem în celula destinație (3,3), respectând următoarele reguli. Din orice celulă (i,j) ne putem deplasa înainte către orice altă celulă (x,y), cu i<=x, j<=y și perechea (i,j) diferită de perechea (x,y). Pe parcursul deplasării se acceptă să ne întoarcem cel mult o dată dintr-o celulă (i,j) către orice altă celulă (x,y), cu x<=i, y<=j, iar perechea (i,j) este diferită de perechea (x,y). De exemplu, din celula (2,2) putem merge înainte către (2,3), (3,2) sau (3,3), și ne putem întoarce la (1,2), (2,1) sau (1,1). Putem alege să ne întoarcem inclusiv când ajungem în celula (3,3). În câte feluri putem ajunge din celula start către cea destinație?

a) 1024; b) 700; c) 2096; d) 2418; e) 2048; f) 260.

Fie un tablou bidimensional M cu l linii și c coloane și un întreg pozitiv k. Valorile pentru elementele din tablou se calculează astfel: M[i][j]=(i+j) mod k, unde x mod y calculează restul împărțirii lui x la y, iar 0<=i<l, 0<=j<c. Câte perechi de elemente care au produsul egal cu suma se găsesc în M? Considerați că l=c=24 și k=6.

a) 9120; b) 384; c) 13824; d) 6912; e) 768; f) 4560.

În urma apelului f(5) se afișează un șir de cifre. Care sunt cifrele de pe pozițiile 14-17, prima poziție fiind numerotată cu 1?

void f(int n)
{
  int i;
  for (i=n; i>=1; i-=2) {
    f(n-1);
    printf("%d", n); // cout << n;
  }
}

a) 2341; b) 4123; c) 4512; d) 1234; e) 1231; f) 2345.

Fie $v$ un vector ce conține $n$ numere întregi. Care este complexitatea minimă a unui algoritm care determină numărul de perechi de indici $(i,j)$, pentru care expresia $\mathrm{abs}(v[i]-v[j])$ are cea mai mare valoare posibilă ($\mathrm{abs}(x)$ reprezintă modulul lui $x$)? a) $O(n)$; b) $O(n\cdot\log(n))$; c) $O(\log(n))$; d) $O(n^2)$; e) $O(2^n)$; f) $O(n!)$.

Fie un arbore cu 10 noduri, numerotate de la 1 la 10 și vectorul său de tați v={0,1,1,2,2,3,3,x,y,z}. Câți vectori de tați valizi și distincți se pot forma dând valori lui x, y și z?

a) 700; b) 567; c) 720; d) 686; e) 729; f) 648.