Enunțul problemei jetoane, de clasa a 7-a, dată în 2004 la ONI, se găsește pe .campion.

Rezumat jetoane

Pentru fiecare cifră de la 0 la 9, Ionel are câte 10 jetoane cu cifra respectivă. El poate forma cu ajutorul lor diferite numere, punându-le unul lângă altul. Pentru două numere date, s și n, trebuie să determinăm câte numere de lungime n și cu suma cifrelor s se pot forma. Valoarea maximă a lui n este 10, de aceea se specifică faptul că sunt 10 jetoane din fiecare fel.

Soluție jetoane

Aceasta este o problemă simplă de programare dinamică. Pentru a forma un număr de lungime k, adăugăm un jeton la finalul unui număr de k - 1 cifre, pentru k natural nenul. Din acest mod de formare al numerelor, putem deduce relația de recurență de care avem nevoie în rezolvarea problemei. Un număr de n cifre cu suma cifrelor s se poate forma prin adăugarea unui jeton cu cifra i la orice număr de n - 1 cifre și cu suma cifrelor s - i, pentru orice i, cu 0 ≤ i ≤ min(s, 9).

Vom reține rezultatele subproblemei în matricea dp, pe care o vom completa în mod obișnuit, de la linia 1 la linia n. Inițializăm elementele de pe linia 1 și coloana cuprinsă între 0 și min(s, 9) cu valoarea 1, pentru că există un singur număr de o cifră cu suma cifrelor egală cu el însuși. Acesta este cazul elementar, când numărul este format dintr-o singură cifră. La fel de bine putea fi considerat caz elementar și cel în care numărul nu are nicio cifră, dar nu avea sens să completez o linie în plus.

Sursă C++ jetoane

Dacă ai vreo nedumerire cu privire la problema jetoane, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!