Informatică #004 Preadmitere Politehnica București 2026
1/5
00:00
Fie un tablou unidimensional v cu n numere întregi distincte și două numere întregi L și R, L≤R. Dorim să determinăm numărul de perechi de indici (i,j) pentru care L≤v[i]+v[j]≤R.Care este complexitatea timp a algoritmului optim care rezolvă problema?
Fie un tablou unidimensional v cu n numere întregi distincte și două numere întregi L și R, L≤R. Dorim să determinăm numărul de perechi de indici (i,j) pentru care L≤v[i]+v[j]≤R.Care este complexitatea timp a algoritmului optim care rezolvă problema?
O(1)
O(n2)
O(nlogn)
O(logn)
O(n2logn)
O(n)
Vectorul se sortează în O(nlogn), apoi se parcurge cu doi indici („two pointers”): pentru fiecare capăt al ferestrei, numărul de perechi cu suma ≤R minus numărul celor cu suma ≤L−1 se determină într-o singură trecere liniară, O(n). Timpul total este dominat de sortare, deci O(nlogn) — sub acest prag nu se poate coborî, întrucât simpla citire a datelor este deja Ω(n), iar orice algoritm bazat pe comparații pentru acest tip de numărare are complexitatea minimă Ω(nlogn).
Se consideră șirul de caractere s care conține primavara2026 și funcția func definită mai jos. Care este rezultatul apelului func(s)?
int func(char s[]) {
int len = strlen(s), i, rez;
rez = 0;
for (i = 0; i < len; i++) {
if (strchr("aeiou", s[i]))
rez++;
}
return rez;
}
8
1
4
3
11
6
Funcția parcurge șirul cu strchr("aeiou", s[i]) și incrementează rez pentru fiecare caracter care este vocală; în primavara2026 vocalele sunt i, a, a, a (cifrele nu se potrivesc cu niciun caracter din "aeiou"), deci func(s) returnează 4.
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?
1925
nu se poate calcula
63
1937
199
1999
Fiecare muchie adăugată poate reduce numărul de componente conexe cu cel mult 1, deci numărul minim de componente se obține când graful este o pădure (fără cicluri): m=2026−2000=26. Pentru maxim, muchiile se concentrează pe cât mai puține noduri: cel mai mic k pentru care Ck2≥2000 este k=64 (din C642=2016≥2000, iar C632=1953<2000); o singură componentă cu aceste 64 de noduri și restul de 2026−64=1962 noduri izolate dau M=1+1962=1963. Rezultă M−m=1963−26=1937.
Fie algoritmul în pseudocod de mai jos, unde determinareMaxim este o funcție care determină elementul cu valoare maximă dintr-un tablou unidimensional cu n elemente, numit vect. Toate tablourile din acest algoritm sunt unidimensionale și indexate de la 0. Tabloul t1 are 10 elemente, iar t2 are n elemente; ambele sunt inițializate cu valori de 0.Ce valoare are elementul cu indexul 2026 din vect, după aplicarea algoritmului, dacă n=4000, iar vect a fost inițializat (înainte de algoritm) cu vect[i] = i % 10, unde x % y reprezintă restul împărțirii lui x la y?
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]
|_
5
4
9
3
6
7
Algoritmul este o sortare prin numărare („counting sort”): primele două bucle construiesc, în t1, poziția finală a fiecărei valori din intervalul 0,…,max dinaintea ultimei scăderi; a treia buclă plasează fiecare element din vect pe poziția lui în t2, obținând șirul sortat crescător; ultima buclă îl inversează, scriind rezultatul descrescător înapoi în vect. Cu vect[i] = i \bmod 10 pentru n=4000, fiecare cifră 0,1,…,9 apare de exact 400 de ori, deci elementul de pe poziția j din t2 (sortat crescător) este ⌊j/400⌋. Din ultima buclă, vect[2026] preia t2[n-2026-1] = t2[1973], adică ⌊1973/400⌋=4.
Două numere naturale distincte, fiecare cu 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.
8100
3996
4104
4005
8091
4095
Notăm primul număr P=abc (cu a∈{1,…,9}, b,c∈{0,…,9}) și al doilea Q=dab (cu d∈{1,…,9}), astfel încât ultimele două cifre ale lui Q sunt exact a și b. Alegerile libere ale lui a,b,c,d dau 9⋅10⋅10⋅9=8100 perechi (P,Q); dintre acestea, P=Q doar când a=b=c=d (9 cazuri), deci rămân 8091 perechi cu numere distincte. Comparând Q−P=100d−90a−9b−c: dacă d>a, atunci 100d≥100a+100, deci Q−P≥10a+100−9b−c≥10+100−81−9=20>0 — P<Q întotdeauna, ceea ce dă ∑a=19(9−a)⋅100=3600 perechi (pentru fiecare a sunt 9−a valori posibile ale lui d și 100 combinații ale lui b,c). Dacă d<a, simetric, Q−P≤−10<0, deci P>Q mereu — niciun caz favorabil. Dacă d=a, condiția devine 10a>9b+c; numărând direct triplele (a,b,c) care o satisfac se obțin 495 de perechi suplimentare. În total, 3600+495=4095 de perechi cu P<Q.