[canonical]: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-006

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-006
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Informatică #006 · Model admitere MateInfo UB

10 grile, din Grafuri și Arbori, Programare Dinamică, Algoritmi Elementari, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

## Teaser gratuit, fără cont

1. Matei vrea să își conecteze cele $40$ de difuzoare bluetooth la telefon. Telefonul și fiecare dispozitiv se pot conecta simultan la cel mult $3$ alte dispozitive, iar latența fiecărei conexiuni este exact o milisecundă.

Care este latența minimă pe care o poate obține Matei între telefon și cel mai depărtat difuzor?

a) $3$
b) $4$
c) $5$
d) $6$
e) $7$
f) $8$

Răspuns corect: b) $4$

Rețeaua optimă e un arbore înrădăcinat în telefon, cu telefonul având $3$ copii direcți și fiecare alt nod având cel mult $2$ copii (a treia conexiune fiind folosită pentru legătura spre părinte). La adâncimea $r$ se pot acoperi cel mult $3\cdot(2^r-1)$ difuzoare: pentru $r=3$ sunt cel mult $21$ difuzoare (insuficient pentru $40$), iar pentru $r=4$ sunt cel mult $45$ (suficient). Latența minimă este deci $4$ milisecunde.

Sursa: Concursul MateInfoUB 2025, secțiunea Informatică, Universitatea din București, 10 mai 2025 · cheie din baremul oficial

2. Țara Numberland are o sută de mii de orașe, numerotate $1,2,\dots,100000$. Între orașul $i$ și orașul $j$: dacă $(i-j)\bmod5\le2$, există o autostradă directă de lungime $|i-j|$; altfel există o cale ferată directă, tot de lungime $|i-j|$ (niciodată ambele).

Distanța dintre două orașe este cea mai mică lungime totală obținută folosind fie numai autostrăzi, fie numai căi ferate (un traseu nu amestecă cele două rețele) — de exemplu, din orașul $1$ în orașul $2$ nu există o cale ferată directă (perechea are o autostradă directă), dar un traseu numai pe calea ferată există totuși prin orașul $5$, cu lungimea totală $7$.

Care este suma distanțelor dintre toate perechile de orașe?

a) $333333333400000$
b) $333343333400000$
c) $166671666750000$
d) $166666666650000$
e) $166666766600000$
f) $366666766600000$

Răspuns corect: d) $166666666650000$

Pentru orice două orașe consecutive, diferența este $1$, iar $1\bmod5=1\le2$, deci există mereu o autostradă directă de lungime $1$ între orașe vecine. Înlănțuind aceste autostrăzi consecutive, distanța „numai cu mașina” dintre oricare orașe $i$ și $j$ este exact $|i-j|$ — minimul teoretic posibil, pe care nicio combinație de căi ferate nu îl poate coborî. Așadar distanța reală dintre orice două orașe este mereu $|i-j|$, iar suma cerută este $\sum_{1\le i<j\le100000}(j-i)=\binom{100001}{3}=166666666650000$.

Sursa: Concursul MateInfoUB 2025, secțiunea Informatică, Universitatea din București, 10 mai 2025 · cheie din baremul oficial

3. Un tată vrea ca numele celor două fete ale sale să fie la aceeași distanță de editare de cuvântul `elma`. Pentru perechile care conțin `*`, cele două cuvinte sunt considerate la aceeași distanță de `elma` dacă există cel puțin un mod de a înlocui fiecare `*` cu o literă astfel încât cele două cuvinte obținute să fie la aceeași distanță de `elma`.

Distanța de editare este numărul minim de adăugări, modificări sau ștergeri ale unui caracter necesare pentru a transforma un cuvânt în altul (de exemplu, distanța dintre `elma` și `ema` este $1$, iar dintre `elma` și `calma` este $2$).

Câte din perechile de mai jos sunt la aceeași distanță de `elma`?

`ema` și `alma` · `riquelma` și `vero` · `dana` și `clema` · `fra*a` și `rex*na` · `fcsb` și `steaua` · `lmx` și `tlma`

a) $0$
b) $1$
c) $2$
d) $3$
e) $4$
f) $5$

Răspuns corect: e) $4$

Distanțele față de `elma`: (`ema`,`alma`) sunt ambele la $1$ — la fel; (`riquelma`,`vero`) sunt ambele la $4$ — la fel; (`dana`,`clema`) sunt la $3$, respectiv $2$ — diferit; pentru (`fra*a`,`rex*na`) există o alegere a celor două `*` care aduce ambele cuvinte la aceeași distanță — la fel; (`fcsb`,`steaua`) sunt ambele la $4$ — la fel; (`lmx`,`tlma`) sunt la $2$, respectiv $1$ — diferit. În total, $4$ din cele $6$ perechi sunt la aceeași distanță de `elma`.

Sursa: Concursul MateInfoUB 2025, secțiunea Informatică, Universitatea din București, 10 mai 2025 · cheie din baremul oficial

4. În țara Numberland există $N$ orașe, fiecare aflat în câte un fus orar întreg, toate diferite între ele. Decalajul orar dintre oricare două orașe este un număr prim.

Care este numărul maxim $N$ de orașe posibil?

a) $3$
b) $4$
c) $5$
d) $13$
e) $15$
f) $17$

Răspuns corect: b) $4$

Dacă două orașe au fusuri de aceeași paritate, decalajul lor e par, deci trebuie să fie exact $2$ (singurul număr prim par) — iar $3$ fusuri de aceeași paritate ar cere ca toate diferențele perechi dintre ele să fie $2$, ceea ce e imposibil (dacă $a<b<c$ diferă toate cu $2$, atunci $c-a=4\ne2$). Deci cel mult $2$ fusuri pot avea fiecare paritate, adică $N\le4$. Un exemplu cu $N=4$: fusurile $0,2,5,7$ — toate decalajele ($2,5,7,3,5,2$) sunt prime. Deci maximul este $4$.

Sursa: Concursul MateInfoUB 2025, secțiunea Informatică, Universitatea din București, 10 mai 2025 · cheie din baremul oficial

5. Dat un număr $X$, Matei poate fie să îl transforme în $5X$, fie — dacă ultima cifră a lui $X$ este $0$ sau $5$ — să îl transforme în $X+1$, $X+2$, $X+3$ sau $X+4$.

Care este numărul minim de transformări pentru a ajunge din $0$ în $202520252025$?

a) $24$
b) $25$
c) $26$
d) $27$
e) $28$
f) $29$

Răspuns corect: e) $28$

Fiecare secvență de transformări corespunde exact scrierii lui $X$ în baza $5$: o operație „$+d$” (cu $d\in\{1,2,3,4\}$) plasează o cifră nenulă, iar o operație „$\times5$” trece la cifra următoare. Numărul minim de pași este (numărul de cifre în baza $5$, minus $1$, pentru operațiile de înmulțire) plus (numărul de cifre nenule, pentru operațiile de adunare). Scriind $202520252025$ în baza $5$ se obțin $17$ cifre, dintre care $12$ sunt nenule, deci minimul este $(17-1)+12=28$.

Sursa: Concursul MateInfoUB 2025, secțiunea Informatică, Universitatea din București, 10 mai 2025 · cheie din baremul oficial