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

Rezumat

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

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

#include <fstream>

#define DMAX 251
#define LGMAX 101

std::ifstream fin("pm.in");
std::ofstream fout("pm.out");

struct BigInt {
    int lg;
    int nr[LGMAX];
};

void print(BigInt a);
void sum(BigInt a, BigInt b, BigInt& s);

int p, m;
BigInt dp[2][DMAX];

int main() {
    bool ln;
    int i, j;
    
    fin >> p >> m;
    if (!p) { // Tratăm separat cazul p == 0:
        if (m == 1)
            fout << "1\n";
        else
            fout << "0\n";
        
        fout.close();
        return 0;
    }

    dp[0][0].nr[0] = 1; dp[0][0].lg = 1; // C(1, 0) = 1
    dp[0][1].nr[0] = 1; dp[0][1].lg = 1; // C(1, 1) = 1

    for (i = 1, ln = true; i <= p; i++, ln ^= true) {
        dp[ln][0].nr[0] = 1; dp[ln][0].lg = 1;
        for (j = 1; j <= m; j++)
            sum(dp[!ln][j - 1], dp[!ln][j], dp[ln][j]);
    }

    print(dp[!ln][m]);
    fout.close();
    return 0;
}

void print(BigInt a) {
    for (int i = a.lg - 1; i >= 0; i--)
        fout << a.nr[i];
    fout << '\n';
}

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

PayPal