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

Rezumat culori

Î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 culori

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 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:

  • dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1
  • dp[i][0] = dp[i - 1][1]
  • dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
  • dp[i][2] = dp[i - 1][1] + dp[i - 1][3]
  • dp[i][3] = dp[i - 1][2] + dp[i - 1][4]
  • dp[i][4] = dp[i - 1][3]

Evident, răspunsul va fi dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3] + 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 dp, pentru a economisi memoria. Putem face asta pentru că linia dp[i] se bazează doar pe linia dp[i - 1].

Sursă C++ culori

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!