Cod sursa(job #1330882)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 31 ianuarie 2015 01:35:30
Problema Pavare2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.52 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>

#define Nmax 105

using namespace std;
int N,A,B;
char kk[105];
///long long DPA[Nmax][Nmax],DPN[Nmax][Nmax];
/// DPA[i][j] in cate feluri putem pava i pietre primele j fiind albe
/// DPN[i][j] in cate feluri putem pava i pietre primele j fiind negre
vector<int> sol;

class nr_mare{
public:
    int nc,cif[Nmax];
    nr_mare()
    {
        nc = 0;
        memset(cif,0,sizeof(cif));
    }
    nr_mare(char c[105])
    {
        int x = strlen(c);
        nc = x;
        for(int i = 0; i < x; ++i)
            this->cif[x-i - 1] = c[i] - 48;
    }
    nr_mare operator =(int b){
        nc = 0;
        while(b)
        {
            cif[nc++] = b % 10;
            b/=10;
        }
        return *this;
    }
    friend nr_mare operator + (nr_mare a,nr_mare b)
    {
        nr_mare c;
        c.nc = a.nc;
        if(b.nc > c.nc)
            c.nc = b.nc;
        int t = 0;
        for(int i = 0; i < c.nc; ++i)
        {
            c.cif[i] = (a.cif[i] + b.cif[i] + t)%10;
            t = (a.cif[i] + b.cif[i] + t) / 10;
        }
        if(t)
            c.cif[c.nc++] = 1;
        return c;
    }
    friend nr_mare operator - (nr_mare a, nr_mare b)
    {
        nr_mare c;
        c.nc = a.nc;
        for(int i = 0; i < c.nc; ++i)
        {
            c.cif[i] = a.cif[i] - b.cif[i];
            if(c.cif[i] < 0)
            {
                c.cif[i] += 10;
                --a.cif[i+1];
            }
        }
        while(c.cif[c.nc - 1] == 0)
            --c.nc;
        return c;
    }
    friend ostream &operator << ( ostream &out, nr_mare &n)
    {
        int i = n.nc;
        while(i--)
            out << n.cif[i];
        return out;
    }
};
nr_mare DPA[Nmax][Nmax],DPN[Nmax][Nmax],K;

bool mai_mare(nr_mare a,nr_mare b)
{
    if(a.nc > b.nc)
        return 1;
    if(a.nc < b.nc)
        return 0;
    for(int i = a.nc - 1; i >= 0; --i)
    {
        if(a.cif[i] > b.cif[i])
            return 1;
        if(a.cif[i] < b.cif[i])
            return 0;
    }
    return 0;
}

void Read(){
    scanf("%d%d%d\n",&N,&A,&B);
    scanf("%s",kk);
    K = nr_mare(kk);
}

void Solve(){
    DPA[1][1] = 1;
    DPN[1][1] = 1;
    for(int i = 2; i <= N; ++i)
    {
        for(int k = 1; k <= B && k < i; ++k)
            DPA[i][1] = DPA[i][1] + DPN[i-1][k]; /// schimb culoarea

        for(int k = 1; k <= A && k < i; ++k)
            DPN[i][1] = DPN[i][1] + DPA[i-1][k]; /// schimb culoarea

        for(int j = 2; j <= A && j <= i; ++j)
            DPA[i][j] = DPA[i-1][j-1]; /// prelungire
        for(int j = 2; j <= B && j <= i; ++j)
            DPN[i][j] = DPN[i-1][j-1]; /// prelungire
    }

    nr_mare ans;
    for(int i = 1; i <= A; ++i)
        ans = ans + DPA[N][i];
    for(int i = 1; i <= B; ++i)
        ans = ans + DPN[N][i];
    cout << ans << "\n";
}

void Print( long long a[Nmax][Nmax] )
{
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= N; ++j)
                printf("%d ",a[i][j]);
            printf("\n");
        }
        printf("\n-------------------------\n");
}

/**void Debug()
{
    Print(DPA);
    Print(DPN);

}**/

void Reconst()
{
    int lastA = 0,lastB = 0;
    long long crt = 0,gata;
    int tip = 0;
    for(int pz = N; pz >= 1; --pz)
    {
        gata = 0;
        if(tip == 0)
        {
            for(int j = A; j >= 1; --j) /// incerc sa pun cati mai multi de 0
            if(mai_mare(K ,DPA[pz][j]))
                K = K - DPA[pz][j];
            else
            {
                for(int k = 1; k <= j; ++k)
                    sol.push_back(0);
                gata = 1;
                pz -= (j - 1);
                tip = 1;
                break;
            }
        }

        if(tip == 1 || !gata)
        {
            if(gata)
                continue;
            for(int j = 1; j <= B; ++j)
            if(mai_mare( K,DPN[pz][j]))
                K = K - DPN[pz][j];
            else
            {
                for(int k = 1; k <= j; ++k)
                    sol.push_back(1);
                pz -= (j - 1);
                tip = 0;
                break;
            }
        }

    }
    for(int i = 0; i < N; ++i)
        printf("%d",sol[i]);
    printf("\n");
}

int main()
{
    freopen("pavare2.in","r",stdin);
    freopen("pavare2.out","w",stdout);

    Read();
    Solve();
    ///Debug();
    Reconst();

    return 0;
}