Problema Culori – OJI 2012, Clasa a 10-a

Problema Culori – OJI 2012, Clasa a 10-a

Rezumat

În problema culori, trebuie să determinăm numărul de moduri în care poate fi pictat un gard cu nn 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: 00 pentru alb, 11 pentru albastru, 22 pentru roșu, 33 pentru verde și 44 pentru galben. Rescriind relațiile date, obținem:

  • 00 poate fi precedat doar de 11
  • 11 poate fi precedat doar de 00 și 22
  • 22 poate fi precedat doar de 11 și 33
  • 33 poate fi precedat doar de 22 și 44
  • 44 poate fi precedat doar de 33

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

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

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

Sursă C++

Problema Culori
#include <fstream>
#define LGMAX 2000
std::ifstream fin("culori.in");
std::ofstream fout("culori.out");
struct BigInt {
int lg;
short int nr[LGMAX];
};
void print(BigInt a);
void init(BigInt& a, int val);
void copy(BigInt& dest, BigInt src);
void sum(BigInt a, BigInt b, BigInt& s);
int n;
BigInt sol;
BigInt dp[2][5];
int main() {
bool ind = 0;
for (int i = 0; i < 5; i++)
init(dp[ind][i], 1);
fin >> n;
for (int i = 2; i <= n; i++, ind ^= 1) {
copy(dp[!ind][0], dp[ind][1]);
sum(dp[ind][0], dp[ind][2], dp[!ind][1]);
sum(dp[ind][1], dp[ind][3], dp[!ind][2]);
sum(dp[ind][2], dp[ind][4], dp[!ind][3]);
copy(dp[!ind][4], dp[ind][3]);
}
for (int i = 0; i < 5; i++)
sum(sol, dp[ind][i], sol);
print(sol);
return 0;
}
void init(BigInt& a, int val) {
if (!val) {
a.lg = 1;
a.nr[0] = 0;
return;
}
a.lg = 0;
while (val) {
a.nr[a.lg++] = val % 10;
val /= 10;
}
}
void print(BigInt a) {
for (int i = a.lg - 1; i >= 0; i--)
fout << a.nr[i];
fout << '\n';
}
void copy(BigInt& dest, BigInt src) {
dest.lg = src.lg;
for (int i = 0; i < src.lg; i++)
dest.nr[i] = src.nr[i];
}
void sum(BigInt a, BigInt b, BigInt& s) {
for (int i = a.lg; i < LGMAX; i++) a.nr[i] = 0;
for (int i = b.lg; i < LGMAX; i++) b.nr[i] = 0;
int t = 0, val;
s.lg = a.lg > b.lg ? a.lg : b.lg;
for (int i = 0; i < s.lg; i++) {
val = a.nr[i] + b.nr[i] + t;
s.nr[i] = val % 10;
t = val / 10;
}
if (t)
s.nr[s.lg++] = t;
}

Dacă ai vreo nedumerire cu privire la problema Culori, lasă un comentariu și te voi ajuta :smile:

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii