Enunțul problemei culori, de clasa a 10-a, dată în 2012 la OJI, se găsește pe InfoArena și PbInfo.

Rezumat

În problema culori, trebuie să determinăm numărul de moduri în care poate fi pictat un gard cu $n$ scânduri, având la dispoziție culorile alb, albastru, roșu, verde și galben. O configurație a culorilor scândurilor de pe gard trebuie să respecte totuși următoarele condiții:

  • După o scândură albă, trebuie să urmeze una albastră.
  • Dacă o scândură albastră, trebuie să urmeze una albă sau roșie.
  • Dacă o scândură roșie, trebuie să urmeze una albastră sau verde.
  • Dacă o scândură verde, trebuie să urmeze una roșie sau galbenă.
  • Dacă o scândură galbenă, trebuie să urmeze una verde.

Soluție

Aceasta este o problemă destul de simplă de programare dinamică. Vom codifica culorile astfel: $0$ pentru alb, $1$ pentru albastru, $2$ pentru roșu, $3$ pentru verde și $4$ pentru galben. Rescriind relațiile date, obținem:

  • $0$ poate fi precedat doar de $1$.
  • $1$ poate fi precedat doar de $0$ și $2$.
  • $2$ poate fi precedat doar de $1$ și $3$.
  • $3$ poate fi precedat doar de $2$ și $4$.
  • $4$ poate fi precedat doar de $3$.

Notând cu $\mathrm{dp}[i][j]$ numărul de moduri în care poate fi vopsit un gard de lungime $i$, astfel încât culoarea ultimei scânduri să fie $j$, obținem următoarele recurențe:

  • $\mathrm{dp}[1][0] = \mathrm{dp}[1][1] = \mathrm{dp}[1][2] = \mathrm{dp}[1][3] = \mathrm{dp}[1][4] = 1$
  • $\mathrm{dp}[i][0] = \mathrm{dp}[i - 1][1]$
  • $\mathrm{dp}[i][1] = \mathrm{dp}[i - 1][0] + \mathrm{dp}[i - 1][2]$
  • $\mathrm{dp}[i][2] = \mathrm{dp}[i - 1][1] + \mathrm{dp}[i - 1][3]$
  • $\mathrm{dp}[i][3] = \mathrm{dp}[i - 1][2] + \mathrm{dp}[i - 1][4]$
  • $\mathrm{dp}[i][4] = \mathrm{dp}[i - 1][3]$

Evident, răspunsul va fi $\mathrm{dp}[i][0] + \mathrm{dp}[i][1] + \mathrm{dp}[i][2] + \mathrm{dp}[i][3] + \mathrm{dp}[i][4]$. Trebuie să implementăm suma pe numere mari, deoarece rezultatele vor crește destul de repede. De asemenea, din cauza numerelor mari este nevoie să reținem doar două linii din matricea $\mathrm{dp}$, pentru a economisi memoria. Putem face asta pentru că linia $\mathrm{dp}[i]$ se bazează doar pe linia $\mathrm{dp}[i - 1]$.

Sursă C++

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