Probleme

Care este valoarea maximă a sumei $a+b$ care se calculează în ultima instrucțiune din funcția h la cel mai adânc nivel al recursivității, pentru apelul h(0, 2026)?

(varianta C/C++)

void h(int a, int b) {
    int m;
    if(a > b) return;
    m = (a + b)/2;
    printf("%d", m % 10); // cout<<m % 10;
    h(a, m - 1);
    h(m + 1, b);
    printf("%d", (a + b) % 10); // cout<<(a + b) % 10;
}

a) $2025$; b) $6$; c) $1013$; d) $2026$; e) $506$; f) $4052$.

Considerăm $G$ un graf neorientat cu $2026$ de noduri și $2000$ de muchii. Fie $m$ numărul minim de componente conexe și $M$ numărul maxim de componente conexe pentru un graf cu proprietățile lui $G$. Ce valoare are $M-m$?

a) $1925$; b) nu se poate calcula; c) $63$; d) $1937$; e) $199$; f) $1999$.

Fie următorul algoritm în pseudocod, unde determinareMaxim este o funcție care determină elementul cu valoare maximă dintr-un tablou unidimensional cu $n$ elemente denumit vect. Toate tablourile folosite în acest algoritm sunt unidimensionale și vor fi indexate de la $0$. Tabloul t1 are $10$ elemente, t2 are $n$ elemente. Atât t1 cât și t2 sunt inițializate cu valori de $0$.

max <- determinareMaxim(vect, n)
pentru i <- 0, n-1, pas=1 executa
|   t1[vect[i]] <- t1[vect[i]] + 1
|_
pentru i <- 1, max, pas=1 executa
|   t1[i] <- t1[i] + t1[i - 1]
|_
pentru i <- n - 1, 0, pas=-1 executa
|   t2[t1[vect[i]] - 1] <- vect[i]
|   t1[vect[i]] <- t1[vect[i]] - 1
|_
pentru i <- 0, n - 1, pas=1 executa
|   vect[i] <- t2[n - i - 1]
|_

Ce valoare are elementul cu indexul $2026$ din vect, după aplicarea algoritmului, dacă n are valoarea $4000$, iar tabloul vect a fost inițializat (înainte de aplicarea algoritmului propus) folosind vect[i] = i % 10, unde x % y reprezintă restul împărțirii lui x la y?

a) $5$; b) $4$; c) $9$; d) $3$; e) $6$; f) $7$.

Fie o matrice de $n$ linii și $n$ coloane. Un număr de elemente $k \ge 1$ din matrice sunt impare, restul fiind pare. Câte submulțimi nevide cu elemente putem construi, astfel încât suma elementelor unei submulțimi să fie pară, dacă $n=4$ și $k=2$?

a) $512$; b) $32768$; c) $16384$; d) $16$; e) $256$; f) $32767$.

Două numere naturale distincte, fiecare având exact $3$ cifre, sunt considerate partenere dacă primele două cifre ale primului număr sunt egale cu ultimele două cifre ale celui de-al doilea număr, în aceeași ordine. Indicați numărul perechilor de numere partenere cu exact $3$ cifre în care primul număr din pereche este strict mai mic decât al doilea.

a) $8100$; b) $3996$; c) $4104$; d) $4005$; e) $8091$; f) $4095$.

Fie următoarea funcție definită în pseudocod, unde x % y reprezintă restul împărțirii lui x la y. Care este rezultatul apelului f(1234567, 0)?

intreg f(intreg n, intreg k) {
    daca (n == 0) returneaza 1;
    rez <- f(n / 10, k);
    daca ((k % 10 - n % 10) != 1)
        rez <- rez + f(n / 10, k * 10 + n % 10);
    returneaza rez;
}

a) $7$; b) $128$; c) $14$; d) $64$; e) $10$; f) $34$.

Fie șirul lui Fibonacci $(F_n)_{n\ge 0}$: $F_0=0$, $F_1=1$, iar pentru $n\ge 2$: $F_n=F_{n-1}+F_{n-2}$. Fie funcția recursivă $f:\mathbb{N}\to\mathbb{Z}$ definită prin $f(0)=0$, $f(1)=1$, iar pentru $n\ge 2$: $f(n)=f(n-1)+(-1)^n\cdot F_{(n \bmod 5)+1}$ (unde mod este restul împărțirii întregi). Ce valoare are $f(2026)$?

a) $5$; b) $4$; c) $0$; d) $8$; e) $-5$; f) $1$.

Fie un șir S format din literele a și b, grupate ca blocuri consecutive după următoarea regulă: 4 de a, apoi 7 de b, apoi 5 de a, apoi 6 de b, apoi 8 de a, apoi 4 de b, apoi 6 de a, apoi 9 de b, adică șirul format după regula descrisă arată astfel: S = aaaabbbbbbbaaaaabbbbbbaaaaaaaabbbbaaaaaabbbbbbbbb. Un subșir al lui S este numit valid dacă conține același număr de caractere a și b și toate caracterele a sunt consecutive și toate caracterele b sunt consecutive (de exemplu subșirurile de forma aaaabbbb, bbbbaaaa, aaabbb, ab, etc. sunt valide). Câte subșiruri valide sunt în S?

a) $34$; b) $34!$; c) $26$; d) $2^{17}$; e) $17$; f) $37$.

Considerăm un graf neorientat complet cu nodurile $\{1,2,\dots,10\}$. Alegem exact $9$ muchii astfel încât subgraful format are următoarele proprietăți: (1) este conex; (2) nu conține niciun ciclu; și (3) nodurile $1$, $2$, $3$ și $4$ au gradul $1$ în subgraful format. Câte astfel de alegeri distincte putem face pentru ca subgraful rezultat să îndeplinească toate cele trei condiții?

a) $6^8$; b) $4!\cdot 6^4$; c) $10^8$; d) $7^8$; e) $10\cdot 6^7$; f) $6^7$.