Grile de informatică pentru admiterea la facultate.

Matricea $s$ este matricea sumelor parțiale. Prima linie și prima coloană sunt nule, iar relația

face ca $s[i][j]$ să fie suma elementelor lui $a$ din dreptunghiul cu colțurile $(1,1)$ și $(i,j)$.

Așadar $s[i][i]$ este numărul de valori $1$ din pătratul de latură $i$. Avem $a[i][j]=1$ exact când $i+j$ este impar, ca pe o tablă de șah cu $a[1][1]=0$. Pentru $i$ par, jumătate dintre cele $i^2$ celule au valoarea $1$. Pentru $i$ impar, celulele cu $0$ sunt cu una mai multe, deci avem $\frac{i^2-1}{2}$ valori $1$. În ambele cazuri, $s[i][i]=\left\lfloor\frac{i^2}{2}\right\rfloor$.

Între $1$ și $20$ sunt $10$ numere impare, iar

Pentru fiecare $i$ impar scădem $1$ înainte de împărțirea la $2$, deci

Prin urmare, programul afișează $1430$.

Nodurile $8$, $9$ și $10$ nu pot avea toate tatăl printre ele. Altfel, urcând din tată în tată, am rămâne mereu în $\{8,9,10\}$ și am intra într-un ciclu, fără să ajungem la rădăcină. Deci cel puțin unul dintre ele are tatăl între $1$ și $7$.

Dacă nodul $10$ are tatăl între $1$ și $7$, atunci $z\le7$ și $x+y+z\le10+10+7=27$. Altfel tatăl din $\{1,\ldots,7\}$ îl are nodul $8$ sau nodul $9$, iar $z\le9$, pentru că niciun nod nu este propriul tată. Suma este atunci cel mult $7+10+9=26$.

Atingem valoarea $27$ pentru $(x,y,z)=(10,10,7)$. Nodurile $8$ și $9$ sunt fiii lui $10$, iar $10$ este fiul lui $7$, deci arborele este valid. Frunzele sunt $4$, $5$, $6$, $8$ și $9$, adică exact cinci.

Prin urmare, valoarea maximă a sumei este $x+y+z=27$.

Pe diagonala principală $j=i$, deci elementele sunt $2i-n$ și

Pe diagonala secundară $j=n+1-i$, deci fiecare element este $i+(n+1-i)-n=1$, iar cele $n$ elemente dau $S_s=n$.

Prin urmare, $S_p=n$ și $S_s=n$.

Un graf conex este eulerian exact când toate vârfurile lui au grad par. Ambele grafuri sunt conexe și rămân conexe când adăugăm muchii, deci căutăm cel mai mare număr de muchii pentru care toate gradele sunt pare.

Pentru G1, graful complet cu $5$ vârfuri are $C_5^2=10$ muchii și toate gradele egale cu $4$, deci este eulerian. G1 are $4$ muchii, deci $M_1=10-4=6$.

Pentru G2, un vârf dintre cele $6$ are gradul cel mult $5$, deci cel mult $4$ dacă gradul trebuie să fie par. Graful rezultat are atunci cel mult $6\cdot4:2=12$ muchii. Atingem această valoare adăugând cele $6$ muchii dintre vârfurile aflate la distanță $2$ pe ciclu, de exemplu $(1,3)$ și $(2,4)$. Fiecare vârf are atunci gradul $4$, deci $M_2=12-6=6$.

Prin urmare, $M_1-M_2=0$.

Desenăm arborele apelurilor. Un apel cu $0<k<n$ face exact două apeluri noi, iar unul cu $k=0$ sau $k=n$ întoarce $1$ fără alte apeluri.

Ramura care întoarce $0$ nu este atinsă niciodată pornind de la $n=9$, $k=5$. Dintr-un apel cu $0<k<n$ rezultă $f(n-1,k-1)$ și $f(n-1,k)$, iar ambele au $0\le k'\le n-1$. Așadar fiecare frunză a arborelui întoarce $1$, iar rezultatul $f(9,5)$ este chiar numărul frunzelor.

Funcția are aceleași valori la capete și aceeași recurență ca numărul combinărilor, $C_n^0=C_n^n=1$ și $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$, deci $f(9,5)=C_9^5=126$.

Într-un arbore în care fiecare nod intern are exact doi fii, nodurile interne sunt cu $1$ mai puține decât frunzele. Arborele are deci $126+125=251$ de noduri.

Prin urmare, funcția este apelată de $251$ de ori, inclusiv la apelul inițial.

La fiecare pas, algoritmul adună la s ultima cifră a lui n și apoi o elimină, deci calculează suma cifrelor. Pentru n = 2026 obținem $6+2+0+2=10$, deci algoritmul afișează 10.

Aplicăm regula produsului. Fiecare dintre cele trei poziții poate fi $0$ sau $1$, independent de celelalte, deci există $2\cdot2\cdot2=2^3=8$ șiruri.

Pornim de la primul element al fiecărei secvențe și găsim ultima lui apariție prin căutare binară. Căutarea binară funcționează pentru că valoarea nu mai reapare după secvența ei. Pozițiile cu aceeași valoare formează un bloc continuu, iar după el toate valorile sunt diferite.

Fiecare căutare costă $O(\log n)$ pași, iar secvența următoare începe imediat după poziția găsită. Pentru cele $k$ secvențe aflăm toate lungimile, deci și numărul care apare de cele mai multe ori, în $O(k\log n)$.

Prin urmare, complexitatea algoritmului este $O(k\log n)$.

La o trecere a metodei bulelor comparăm pe rând perechile de elemente vecine, de la stânga la dreapta, și le interschimbăm pe cele aflate în ordine greșită.

Comparăm $4$ cu $1$ și le interschimbăm, obținând $[1,4,3]$.
Comparăm $4$ cu $3$ și le interschimbăm, obținând $[1,3,4]$.

Prin urmare, după prima trecere vectorul devine $[1,3,4]$.

În C, C++ și Pascal, un identificator este format din litere, cifre și caracterul _ și nu începe cu o cifră. Astfel, 3.14 și 2x încep cu o cifră, iar a+b, x,y și suma-total conțin caracterele nepermise +, , și -.

Prin urmare, numele valid este suma2total.