[canonical]: https://grile.online/informatica/programare-dinamica

> Pagina completă: https://grile.online/informatica/programare-dinamica
> 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.


# Grile Programare dinamică · Informatică

5 grile, în 2 seturi, cu explicații.

## Teaser gratuit, fără cont

1. Meșterul Piperel are $10$ țevi cu lungimile de $7,5,3,2,3,10,7,4,9$ și $6$ metri, pe care trebuie să le îmbine într-o singură țeavă. De fiecare dată poate îmbina doar două țevi (în orice ordine alege), iar țeava nouă e așezată lângă celelalte. Îmbinarea a două țevi cu lungimile $x$ și $y$ metri costă $x+y$ RON și produce o țeavă nouă de $x+y$ metri.

Calculați costul minim necesar pentru a îmbina toate cele $10$ țevi într-una singură.

a) $56$
b) $180$
c) $194$
d) $278$
e) $325$

Răspuns corect: b) $180$

Costul total minim se obține îmbinând mereu cele două țevi cele mai scurte disponibile (strategie de tip Huffman): țevile mai scurte apar în mai multe îmbinări ulterioare, deci trebuie combinate cât mai devreme. Aplicând acest procedeu asupra lungimilor date se obține un cost minim de $180$ RON.

2. Cristian și Vlad au un pachet de $52$ de cărți de joc și joacă un joc: se aleg inițial $N$ cărți din cele $52$; Cristian ia primul cărți din acest pachet, apoi jucătorii alternează. La fiecare tură, jucătorul curent ia exact $2$, $3$ sau $5$ cărți. Dacă la începutul unei ture rămân $0$ sau $1$ cărți, jucătorul căruia îi vine rândul nu are nicio mutare validă și pierde.

Ambii joacă optimal. Se joacă $5$ partide, cu $N=10$, $N=20$, $N=30$, $N=40$ și $N=50$. În câte dintre aceste partide câștigă Cristian?

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

Răspuns corect: d) $4$

Notând cu $W(n)$ adevărat dacă jucătorul aflat la mutare câștigă având $n$ cărți rămase ($W(0)$ și $W(1)$ false, iar $W(n)$ adevărat dacă există o mutare de $2$, $3$ sau $5$ spre o poziție $W$ falsă), se calculează prin programare dinamică: Cristian (primul mutător) câștigă pentru $N=10,20,30,40$ și pierde doar pentru $N=50$ — deci câștigă în $4$ din cele $5$ partide.

3. Într-un vis, Mariei i se dezvăluie prețul unui caiet pentru următoarele $10$ zile: $15,31,5,15,20,5,17,23,10,18$ lei. În fiecare zi poate cumpăra un caiet (dacă nu are niciunul) sau vinde caietul deținut; nu poate deține $2$ caiete simultan, dar poate cumpăra și vinde de oricâte ori dorește.

Știind că nu deține niciun caiet în prima zi, care este suma maximă de bani pe care o poate câștiga?

a) $26$
b) $18$
c) $31$
d) $57$
e) $72$

Răspuns corect: d) $57$

Cu tranzacții nelimitate și cel mult un caiet deținut simultan, profitul maxim este suma tuturor creșterilor consecutive de preț din șir: $15\to31$ ($+16$), $5\to15$ ($+10$), $15\to20$ ($+5$), $5\to17$ ($+12$), $17\to23$ ($+6$), $10\to18$ ($+8$). Suma acestor câștiguri este $16+10+5+12+6+8=57$ lei.

4. Radu are $8$ cabluri așezate în linie, cu lungimile $4,2,7,3,5,1,6,2$ metri. La fiecare pas poate îmbina doar două cabluri alăturate (vecine în linie), rezultatul luând locul lor în linie, cu lungimea egală cu suma celor două. Costul unei îmbinări este egal cu suma lungimilor celor două cabluri îmbinate.

Care este costul minim pentru a îmbina toate cele $8$ cabluri într-unul singur?

a) $85$
b) $87$
c) $89$
d) $91$
e) $93$
f) $136$

Răspuns corect: c) $89$

Spre deosebire de o îmbinare liberă (unde strategia optimă ar fi tip Huffman, mereu cele mai scurte două disponibile, indiferent de poziție), aici pot fi îmbinate doar cabluri vecine — problema se rezolvă prin programare dinamică pe intervale: costul minim de a topi un interval $[i,j]$ într-un singur cablu este minimul, peste toate punctele de tăiere, al sumei costurilor celor două subintervale plus suma lungimilor din tot intervalul $[i,j]$. Aplicând această recurență pe cele $8$ lungimi date se obține costul minim $89$ RON (strategia Huffman liberă, care ignoră restricția de adiacență, ar da eronat $85$).

5. Bianca și Cezar joacă un joc cu $N$ jetoane, mutând alternativ, Bianca prima. La fiecare tură, jucătorul curent ia exact $1$, $4$ sau $5$ jetoane; cel care ia ultimul jeton câștigă.

Ambii joacă optimal. Pentru câte valori ale lui $N$ din mulțimea $\{50,51,\dots,99\}$ câștigă Bianca (prima mutătoare)?

a) $13$
b) $25$
c) $36$
d) $37$
e) $38$
f) $40$

Răspuns corect: d) $37$

Notând cu $W(n)$ adevărat dacă jucătorul aflat la mutare câștigă cu $n$ jetoane rămase ($W(0)$ fals, iar $W(n)$ adevărat dacă există o mutare de $1$, $4$ sau $5$ spre o poziție $W$ falsă), poziția e pierzătoare exact când $n\bmod8\in\{0,2\}$ — un tipar periodic de perioadă $8$ confirmat prin programare dinamică. Numărând valorile $N\in\{50,\dots,99\}$ pentru care mutătorul (Bianca) NU e într-o poziție pierzătoare, Bianca câștigă pentru exact $37$ din cele $50$ de valori.

## Seturi care conțin acest capitol

- [Informatică #005](https://grile.online/informatica/rezolva?set=informatica-mateinfoub-2025-1)
- [Informatică #006](https://grile.online/informatica/rezolva?set=informatica-mateinfoub-2025-2)