Cod sursa(job #2325032)

Utilizator dorupopDoru Pop dorupop Data 21 ianuarie 2019 21:22:42
Problema Pavare2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <fstream>
#include <cstring>
using namespace std;
int n, p, q, lng, st, i, j, k[105];
int a[105][105][105], b[105][105][105], c[105];
char s[105];

void suma (int A[], int B[], int C[])
{
    int t=0, k=0, i=0;
    for (i=1;i<=A[0] || i<=B[0];i++) {
        k=A[i]+B[i]+t;
        C[i]=k%10;
        t=k/10;
    }
    C[0]=i-1;
    if (t!=0) {
        C[0]++;
        C[i]=t;
    }
}

void dif (int A[], int B[], int C[])
{
    int t=0, k=0, i=0;
    C[0]=A[0];
    for (i=1;i<=A[0];i++) {
        if (A[i]-t<B[i]) {
            k=10+A[i]-t-B[i];
            t=1;
        } else {
            k=A[i]-t-B[i];
            t=0;
        }
        C[i]=k;
    }
    while (C[C[0]]==0)
        C[0]--;
}

int cmp (int A[], int B[])
{
    int i=0;
    if (A[0]>B[0])
        return 1;
    if (A[0]<B[0])
        return -1;
    for (i=A[0];i>=1;i--) {
        if (A[i]>B[i])
            return 1;
        if (A[i]<B[i])
            return -1;
    }
    return 0;
}

int main () {
    ifstream fin ("pavare2.in");
    ofstream fout ("pavare2.out");
    fin>>n>>p>>q;
    fin>>s+1;
    k[0]=strlen(s+1);
    for (i=k[0];i>=1;i--) {
        k[k[0]-i+1]=s[i]-'0';
    }

    a[0][0][1]=1;
    a[0][0][0]=1;
    b[0][0][1]=1;
    b[0][0][0]=1;
    a[1][1][1]=1;
    a[1][1][0]=1;
    a[1][0][1]=1;
    a[1][0][0]=1;
    b[1][1][1]=1;
    b[1][1][0]=1;
    b[1][0][1]=1;
    b[1][0][0]=1;

    for (i=2;i<=n;i++) {
        for (j=1;j<=min(i,p);j++) {
            memcpy (a[i][j], b[i-j][0], sizeof(b[i-j][0]));
            suma(a[i][0], a[i][j], a[i][0]);
        }
        for (j=1;j<=min(q,i);j++) {
            memcpy (b[i][j], a[i-j][0], sizeof(a[i-j][0]));
            suma(b[i][0], b[i][j], b[i][0]);
        }

    }

    suma(a[n][0], b[n][0], c);
    for(i=c[0];i>=1;i--)
        fout<<c[i];
    fout<<"\n";

    lng=n;
    st=0;
    while (lng!=0) {
        if (st==0) {
            if (cmp(k, a[lng][0])==1) {
                dif(k, a[lng][0], k);
            } else {
                for (i=p;i>=1;i--) {
                    if (cmp(a[lng][i], k)==1 || cmp(a[lng][i], k)==0) {
                        for (int cnt=1;cnt<=i;cnt++)
                            fout<<st;
                        lng-=i;
                        break;
                    } else {
                        dif(k, a[lng][i], k);
                    }
                }
            }
        } else {
            if (cmp(k, b[lng][0])==1) {
                dif(k, b[lng][0], k);
            } else {
                for (i=1;i<=q;i++) {
                    if (cmp(b[lng][i], k)==1 || cmp(b[lng][i], k)==0) {
                        for (int cnt=1;cnt<=i;cnt++)
                            fout<<st;
                        lng-=i;
                        break;
                    } else {
                        dif(k, b[lng][i], k);
                    }
                }
            }
        }
        st=1-st;
    }

    return 0;
}