Cod sursa(job #1655478)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 18 martie 2016 00:10:00
Problema Pavare2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.56 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 105
#define NRC 35
FILE *f=fopen("pavare2.in","r"), *g=fopen("pavare2.out","w");

using namespace std;

int N, K[NRC+2], a[2][MAXN][MAXN][NRC+2], sum[2][MAXN][MAXN][NRC+2], AB[2];
int UNU[NRC+2], T[NRC+2], sol0[NRC+2];

    // a   [ 0/1 ][ cate ori ][ de pe poz ]
    // sum [ 0/1 ][ de pe poz ] (suma cu i cate ori)

int op( int Q ){ return (Q+1)%2; } // 0->1 1->0

void IAVAL( int Q[], int W[] ){
int i;

    Q[0] = W[0];
    for(i=1;i<=Q[0];i++)
        Q[i] = W[i];

}

void ADUNA( int Q[], int W[], int Y[] ){
int i, lY = max( Q[0], W[0] ), tr;

    Y[0] = lY;
    for(i=1;i<=Y[0];i++)
        Y[i] = 0;

    for(i=1;i<=Q[0];i++)
        Y[i] += Q[i];

    for(i=1;i<=W[0];i++)
        Y[i] += W[i];

    tr = 0;
    for(i=1;i<=Y[0];i++){

        Y[i] += tr;
        tr = Y[i] / 10;
        Y[i] %= 10;

    }

    while( tr > 0 ){

        Y[0] ++;
        Y[ Y[0] ] = tr % 10;
        tr /= 10;

    }

}

void AFIS( int Q[] ){
int i;

    for(i=Q[0];i>=1;i--)
        fprintf(g,"%d",Q[i]);
        fprintf(g,"\n");
}

void SCADE( int Q[], int W[] ){
int i, tr;

    for(i=1;i<=W[0];i++)
        Q[i] -= W[i];

    tr = 0;
    for(i=1;i<=W[0];i++){

        Q[i] += tr;
        tr = 0;

        if( Q[i] < 0 ){

            Q[i] += 10;
            tr = -1;

        }

    }
    if( tr == -1 )
        Q[ W[0] + 1 ] += tr;

    while( Q[ Q[0] ] == 0 && Q[0] >= 2 )
        Q[0] --;

}

void Calculare_a(){
int poz, zu, nr, i;

    for(zu=0;zu<=1;zu++)
        for(nr=1;nr<=AB[zu];nr++)
            IAVAL( a[zu][nr][N+1], UNU );

            IAVAL( sum[0][N][N+1], UNU);
            IAVAL( sum[1][N][N+1], UNU);

    for( poz = N; poz >= 1; poz -- )
        for( zu = 0; zu <= 1; zu ++ ){

            for( nr = 1; nr <= AB[zu] && poz + nr - 1 <= N; nr ++ ){

                if( nr == 1 )
                    IAVAL( a[zu][nr][poz], sum[op(zu)][N][poz+1] );
                else
                    IAVAL( a[zu][nr][poz], a[zu][nr-1][poz+1] );

                ADUNA( sum[zu][nr][poz], a[zu][nr][poz], T );
                IAVAL( sum[zu][nr][poz], T);

            }

            for( i = 2; i <= N; i++ ){

                ADUNA( sum[zu][i][poz], sum[zu][i-1][poz], T );
                IAVAL( sum[zu][i][poz], T );

            }

        }

    ADUNA( sum[0][N][1], sum[1][N][1], T );
    AFIS(T);
}

bool COMP( int Q[], int W[] ){  // if( Q <= W ) return 1;

    if( Q[0] < W[0] )
        return 1;

    if( Q[0] > W[0] )
        return 0;

    for( int i = Q[0]; i >= 1; i-- ){
        if( Q[i] < W[i] )
            return 1;
        if( Q[i] > W[i] )
            return 0;
    }


    return 1;
}

void DezmembrareK(){
int i, zu, nr[2];

    // nr[0] = lung de pana acum de 0

    nr[0] = 0;
    nr[1] = 0;

    for(i=1;i<=N;i++){

        IAVAL( sol0, sum[ 0 ][ AB[0] - nr[0] ][i] );

        if( COMP( K, sol0) ){    // if( K <= sol0 ) urmeaza un 0

            fprintf(g,"0");
            nr[0] ++;
            nr[1] = 0;

        }
        else{

            SCADE( K, sol0 );
            fprintf(g,"1");
            nr[1] ++;
            nr[0] = 0;

        }

    }

}

void Citire(){
int i;
char s[NRC+2];

    fscanf(f,"%d %d %d\n%s\n",&N,&AB[0],&AB[1],s);

    K[0] = strlen(s);
    for(i=1;i<=K[0];i++)
        K[i] = s[ K[0]-i ]-'0';

    UNU[0] = 1;
    UNU[1] = 1;

}

int main(){

    Citire();
    Calculare_a();
    DezmembrareK();

return 0;
}