Problema culori – OJI 2012, Clasa a 10-a

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

#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() {
    fin >> n;

    bool ind = false;
    for (int i = 0; i < 5; i++)
        init(dp[ind][i], 1);

    for (int i = 2; i <= n; i++, ind ^= true) {
        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);

    fout.close();
    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;
}

#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() {

fin >> n;

bool ind = false;

for (int i = 0; i < 5; i++)

init(dp[ind][i], 1);

for (int i = 2; i <= n; i++, ind ^= true) {

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);

fout.close();

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 🙂

Îț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!

Problema culori – OJI 2012, Clasa a 10-a

Rezumat culori

Soluție culori

Sursă C++ culori

Îți place conținutul acestui site?

Similare

Introdu Comentariu Anulează răspunsul

Problema culori – OJI 2012, Clasa a 10-a

Rezumat culori

Soluție culori

Sursă C++ culori

Îți place conținutul acestui site?

Partajează asta:

Similare

Introdu Comentariu Anulează răspunsul