Rezolvare admitere Politehnica București (UPB) 2025, Informatică, Varianta S — pas cu pas, cu cod testat

Întrebarea 1 (9 p)

Cerința, pe scurt: Funcția este_lucratoare(zi) întoarce adevărat dacă zi % 7 nu e nici 0, nici 6; zile_lucratoare(an) numără zilele lucrătoare din 1..an. Cât întoarce zile_lucratoare(365)? Variante: 261, 258, 262, 200, 250, 251.

Ce se cere: Să numeri câte numere din 1..365 dau la împărțirea cu 7 restul 1, 2, 3, 4 sau 5.

Noțiuni: operatorul % · numărare pe perioade · funcții care întorc o valoare logică

Rezolvare pas cu pas

1. O zi e „lucrătoare” când restul la 7 este 1, 2, 3, 4 sau 5 — adică 5 resturi din 7.
2. 365 = 52·7 + 1, deci zilele 1..364 formează 52 de săptămâni complete, fiecare cu exact 5 zile lucrătoare: 52·5 = 260.
3. Rămâne ziua 365, cu 365 % 7 = 1 — este lucrătoare.
4. Total: 260 + 1 = 261.

int este_lucratoare(int zi) {
  return (zi % 7 != 0 && zi % 7 != 6);
}

int zile_lucratoare(int an) {
  int zile = 0;
  for (int zi = 1; zi <= an; zi++) {
    if (este_lucratoare(zi))
      zile++;
  }
  return zile;
}

Răspuns final: a — 261

Verificare: Am rulat funcțiile din subiect: zile_lucratoare(365) = 261; o numărare separată pe resturi (r = 1..5) dă tot 261.

Întrebarea 2 (9 p)

Cerința, pe scurt: Ce valoare primește m după m=(a+b+abs(a-b))/2? Variante: maximul dintre a și b, minimul, a+b, a-b, a, b.

Ce se cere: Să simplifici expresia în cele două cazuri posibile: a ≥ b și a < b.

Noțiuni: modulul unui număr · împărțire întreagă · analiză pe cazuri

Rezolvare pas cu pas

1. Dacă a ≥ b: abs(a-b) = a-b, deci m = (a+b+a-b)/2 = 2a/2 = a.
2. Dacă a < b: abs(a-b) = b-a, deci m = (a+b+b-a)/2 = 2b/2 = b.
3. În ambele cazuri m este cel mai mare dintre a și b. Numărătorul e mereu par (2a sau 2b), deci împărțirea întreagă nu pierde nimic.

Răspuns final: a — maximul dintre a și b

Verificare: Am rulat instrucțiunea pentru toate perechile a, b din [-60, 60]: m a fost de fiecare dată egal cu maximul, iar fiecare dintre celelalte cinci variante a fost contrazisă de cel puțin o pereche.

Întrebarea 3 (9 p)

Cerința, pe scurt: Pentru n=6, a=(2,1,5,3,4,6), b=(1,3,5,2,4,6) se execută for(i=0;i<n;i++) a[i]=a[b[n-i-1]-1]; apoi for(i=0;i<n;i++) b[n-i-1]=b[a[i]-1];. Ce conțin a și b la final?

Ce se cere: Să simulezi pas cu pas, ținând cont că tablourile se modifică pe loc (un element deja schimbat poate fi citit mai târziu).

Noțiuni: tablouri unidimensionale · indici calculați · modificare pe loc

Rezolvare pas cu pas

1. Prima buclă (b nu se schimbă): i=0: a[0]=a[b[5]-1]=a[5]=6 → a=(6,1,5,3,4,6).
2. i=1: a[1]=a[b[4]-1]=a[3]=3; i=2: a[2]=a[b[3]-1]=a[1]=3 (valoarea nouă!); i=3: a[3]=a[b[2]-1]=a[4]=4.
3. i=4: a[4]=a[b[1]-1]=a[2]=3; i=5: a[5]=a[b[0]-1]=a[0]=6. După prima buclă a=(6,3,3,4,3,6) — rămâne așa până la final.
4. A doua buclă (b se modifică de la coadă spre început): i=0: b[5]=b[a[0]-1]=b[5]=6; i=1: b[4]=b[2]=5; i=2: b[3]=b[2]=5.
5. i=3: b[2]=b[3]=5; i=4: b[1]=b[2]=5; i=5: b[0]=b[5]=6. Deci b=(6,5,5,5,5,6).

for(i=0;i<n;i++) a[i]=a[b[n-i-1]-1];
  for(i=0;i<n;i++) b[n-i-1]=b[a[i]-1];

Răspuns final: a — a=(6,3,3,4,3,6), b=(6,5,5,5,5,6)

Verificare: Am rulat exact cele două bucle din subiect pe datele din enunț; programul afișează a=(6,3,3,4,3,6) și b=(6,5,5,5,5,6).

Întrebarea 4 (9 p)

Cerința, pe scurt: Un arbore cu 9 noduri are vectorul de tați t=(0,1,1,2,1,2,2,5,5). Câte frunze are? Variante: 6, 5, 4, 3, 7, 9.

Ce se cere: Să găsești nodurile care nu sunt tatăl niciunui alt nod.

Noțiuni: vector de tați · rădăcină · frunză

Rezolvare pas cu pas

1. t[1]=0, deci 1 este rădăcina.
2. Tații care apar în vector (fără 0) sunt 1, 2 și 5: fiii lui 1 sunt 2, 3, 5; fiii lui 2 sunt 4, 6, 7; fiii lui 5 sunt 8, 9.
3. Nodurile care nu apar ca tată sunt frunzele: 3, 4, 6, 7, 8, 9 — în total 6.

Răspuns final: a — 6

Verificare: Un program care marchează fiecare t[i] ca „are fiu” găsește frunzele 3, 4, 6, 7, 8, 9 (6 frunze) și o singură rădăcină.

Întrebarea 5 (9 p)

Cerința, pe scurt: Cu backtracking se generează în ordine crescătoare numerele naturale scrise doar cu cifrele 0–6 (primele: 0, 1, …, 6, 10, 11, 12). Care este al 256-lea număr generat? Variante: 513, 501, 555, 466, 444, 503.

Ce se cere: Să observi că șirul este, de fapt, numărarea în baza 7 și să scrii în baza 7 poziția potrivită.

Noțiuni: backtracking · baze de numerație · ordine crescătoare

Rezolvare pas cu pas

1. Numerele cu cifre 0–6, în ordine crescătoare, sunt exact scrierile în baza 7 ale lui 0, 1, 2, 3, … (de exemplu „10” este al 8-lea număr, adică 7 scris în baza 7).
2. Primul număr generat este 0, deci al 256-lea este scrierea în baza 7 a lui 255.
3. 255 = 5·49 + 10, iar 10 = 1·7 + 3. Deci 255 = 5·7² + 1·7 + 3, adică 513 în baza 7.

Răspuns final: a — 513

Verificare: Am implementat backtracking-ul (pe lungimi, fără 0 în față) și l-am comparat cu enumerarea directă a numerelor naturale care au toate cifrele ≤ 6: primele 300 coincid, primele 10 sunt cele din enunț, iar al 256-lea este 513.

Întrebarea 6 (9 p)

Cerința, pe scurt: Din n=7 fete și m=5 băieți se formează k=3 perechi fată–băiat. În câte moduri? Variante: 2100, 35, 60, 210, 2880, 700.

Ce se cere: Să alegi fetele, să alegi băieții și apoi să-i potrivești între ei.

Noțiuni: combinări · permutări · regula produsului

Rezolvare pas cu pas

1. Alegem cele 3 fete care dansează: C(7,3) = 35.
2. Alegem cei 3 băieți: C(5,3) = 10.
3. Potrivim cele 3 fete cu cei 3 băieți: 3! = 6 moduri.
4. Total: 35 · 10 · 6 = 2100. (Echivalent: A(7,3)·C(5,3) = 210·10 = 2100.)

Răspuns final: a — 2100

Verificare: Forță brută: am enumerat toate mulțimile de 3 perechi (fată, băiat) dintre cele 35 de perechi posibile și le-am păstrat doar pe cele fără fată sau băiat repetat — 2100, la fel ca formula.

Întrebarea 7 (9 p)

Cerința, pe scurt: Tipul Complex are câmpurile re, im; tipul ComplexSecv are n și tabloul elemente[100] de Complex. Pentru variabila CS, ce expresie testează că primul element din secvență este număr real?

Ce se cere: Să accesezi corect primul element din tablou (indice 0 în C/C++) și să verifici că partea imaginară e 0.

Noțiuni: struct / record · tablou de structuri · operatorul . · număr complex real

Rezolvare pas cu pas

1. Un număr complex re + im·i este real exact când im = 0.
2. Tabloul se află în câmpul elemente, deci primul element este CS.elemente[0] în C/C++ (CS.elemente[1] în Pascal, unde indicii încep de la 1).
3. Expresia corectă: CS.elemente[0].im==0.
4. Varianta b testează partea reală (re==0), adică dacă numărul e pur imaginar. Variantele c–f nu compilează: elemente e un tablou (nu are câmpul im fără indice), iar CS nu are câmpul im.

typedef struct {
    int re, im;
} Complex;
typedef struct {
    int n;
    Complex elemente[100];
} ComplexSecv;

Răspuns final: a — CS.elemente[0].im==0 (Pascal: CS.elemente[1].im=0)

Verificare: Am compilat tipurile din subiect: expresia a dă adevărat pentru 5 și fals pentru 2i; varianta b dă greșit „real” pentru 2i; variantele c, d, e, f sunt respinse de compilator.

Întrebarea 8 (9 p)

Cerința, pe scurt: Într-o matrice n×n de numere reale, fiecare linie și fiecare coloană sunt sortate crescător. Care este complexitatea timp minimă a unui algoritm care verifică dacă un x dat apare în matrice? Variante: O(n), O(n·log n), O(n²), O(log n), O(n²·log n), O(1).

Ce se cere: Să găsești un algoritm rapid și să argumentezi de ce nu se poate mai repede de atât.

Noțiuni: complexitate timp · căutare în scară (saddleback search) · matrice sortată

Rezolvare pas cu pas

1. Pornim din colțul dreapta-sus a[0][n-1]. Dacă e egal cu x, am terminat.
2. Dacă a[i][j] > x, tot ce e sub el pe coloana j e și mai mare, deci eliminăm coloana: j--.
3. Dacă a[i][j] < x, tot ce e în stânga lui pe linia i e și mai mic, deci eliminăm linia: i++.
4. La fiecare pas dispare o linie sau o coloană, deci facem cel mult 2n−1 comparații: O(n).
5. Mai repede nu se poate: elementele de pe diagonala secundară (i + j = n−1) nu sunt ordonate între ele de proprietatea din enunț — oricare dintre ele poate fi x — deci în cel mai rău caz trebuie privite toate cele n. Astfel O(n) este complexitatea minimă.

bool cauta(const std::vector<std::vector<double>>& a, int n, double x) {
  int i = 0, j = n - 1;           // pornim din colțul dreapta-sus
  while (i < n && j >= 0) {
    comparatii++;
    if (a[i][j] == x) return true;
    if (a[i][j] > x) j--;         // tot ce e sub a[i][j] pe coloana j e și mai mare
    else i++;                     // tot ce e în stânga lui a[i][j] pe linia i e și mai mic
  }
  return false;
}

Complexitate: O(n) timp (cel mult 2n−1 comparații), O(1) memorie suplimentară.

Răspuns final: a — O(n)

Verificare: Am rulat căutarea în scară pe 48 000 de interogări (matrici aleatoare sortate pe linii și coloane, n=1..40), comparând cu căutarea completă: niciun răspuns greșit și niciodată mai mult de 2n−1 comparații. Limita inferioară (de ce nu există ceva sub O(n)) este argumentul de la pasul 5, nu un test.

Întrebarea 9 (9 p)

Cerința, pe scurt: power(x,n) întoarce 1 dacă n==0, x*power(x,n/2) dacă n e par, altfel power(x,(n-1)/2). Cât este power(2,2025)? Variante: 8, 1024, 128, 4096, 16, 2048.

Ce se cere: Să urmărești lanțul de apeluri și să numeri de câte ori se înmulțește cu x (doar la n par!).

Noțiuni: recursivitate · paritate · urmărirea apelurilor

Rezolvare pas cu pas

1. Funcția seamănă cu ridicarea rapidă la putere, dar are o greșeală: pe ramura n impar nu înmulțește cu x, iar pe ramura n par înmulțește o singură dată (nu ridică la pătrat).
2. Lanțul: 2025 (impar) → 1012 (par, ×2) → 506 (par, ×2) → 253 (impar) → 126 (par, ×2) → 63 → 31 → 15 → 7 → 3 → 1 (toate impare) → 0, care întoarce 1.
3. S-a înmulțit cu 2 de exact 3 ori (la 1012, 506 și 126): 2³ = 8.

int power(int x, int n) {
    if(n==0)
       return 1;
    if(n%2==0)
       return x * power(x, n/2);
    else
       return power(x, (n-1)/2);
}

Răspuns final: a — 8

Verificare: Am rulat funcția exact cum e tipărită: power(2,2025) = 8. O copie instrumentată afișează lanțul 2025 1012 506 253 126 63 31 15 7 3 1 0 și numără 3 înmulțiri.

Întrebarea 10 (9 p)

Cerința, pe scurt: Un program își deschide propriul fișier sursă și citește linii într-o buclă (5 linii în C/C++, 7 în Pascal), apoi afișează ultima linie citită. Ce afișează? Variante: int i = 0; / i := 0;, nimic, } / end., i++; / inc(i);, int main() { / begin, return 0; / writeln(sir);.

Ce se cere: Să numeri liniile fișierului sursă, inclusiv liniile goale, și să găsești linia citită ultima.

Noțiuni: fișiere text · fgets / getline / readln · numărarea liniilor

Rezolvare pas cu pas

1. Bucla citește câte o linie la fiecare pas, deci după ea sir conține linia a 5-a (C/C++) sau a 7-a (Pascal).
2. main.c: 1 #include <stdio.h>, 2 linie goală, 3 int main() {, 4 FILE * file = …, 5 int i = 0;.
3. main.cpp: 1 #include <iostream>, 2 #include <fstream>, 3 std::ifstream file("main.cpp");, 4 int main() {, 5 int i = 0;.
4. main.pas: 1 program Program1;, 2 var …, 3 i: Integer;, 4 begin, 5 assign(…), 6 reset(f);, 7 i := 0;.
5. În toate cele trei variante se afișează linia de inițializare a lui i.

#include <iostream>
#include <fstream>
std::ifstream file("main.cpp");
int main() {
  int i = 0;
  char sir[128];
  while(i < 5) {
    file.getline(sir, 128);
    i++;
  }
  file.close();
  std::cout << sir;
  return 0;
}

Răspuns final: a — C/C++: int i = 0; / Pascal: i := 0;

Verificare: Am salvat main.c și main.cpp exact ca în subiect, le-am compilat (gcc/g++ 13.3) și le-am rulat în același director: ambele afișează „ int i = 0;”. Pentru main.pas compilatorul Pascal nu e disponibil, așa că am citit a 7-a linie a fișierului cu un program care imită bucla readln: „ i := 0;”.