Enunțul problemei pm, de clasa a 8-a, dată în 2008 la ONI, se găsește pe PbInfo, .campion și InfoArena.

Rezumat pm

Numim o secvență PM un șir format doar din semne plus și minus, care NU conține două semne minus alăturate. Să se afișeze numărul de secvențe PM cu p semne plus și m semne minus. De exemplu, există 6 secvențe PM cu 3 plusuri și 2 minusuri: -+-++, -++-+, -+++-, +-+-+, +-++-, ++-+-.

Soluție pm

Problema se poate rezolva prin programare dinamică, dar soluția mai interesantă este cea combinatorială. Să presupunem că avem un șir format din p semne plus. În acest șir, trebuie să inserăm m semne minus. Există p + 1 poziții unde acestea pot fi inserate astfel încât să nu existe două alăturate: la început, la final și între oricare două semne plus consecutive. Ei bine, numărul de moduri în care putem pune m semne minus pe p + 1 poziții este egal cu $C_{p + 1}^{m}$ (combinări de $p+1$ luate câte $m$).

Am calculat numărul de combinări folosind Triunghiul lui Pascal. Pentru a mă încadra în memorie am reținut o matrice dp cu numai două linii, deoarece la orice pas avem nevoie doar de rezultatele de pe linia anterioară. De asemenea, a fost necesară implementarea operațiilor pe numere mari (de fapt, doar suma).

Sursă C++ pm

Dacă ai vreo nedumerire cu privire la problema pm, 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!