Cod sursa(job #497955)

Utilizator cont_de_testeCont Teste cont_de_teste Data 3 noiembrie 2010 19:50:08
Problema Bile2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std ;

#define max(a,b)((a)>(b)?(a):(b))
#define FIN "bile2.in"
#define FOU "bile2.out"

# define verf( X, i ) ( i <= X[0] ? X[i] : 0 )
# define A ( *this )

class Mare : protected vector < int > {
public :
    Mare ( ) ;
    Mare operator * ( Mare& ) ;
    Mare operator + ( Mare& ) ;
    void operator += ( Mare& ) ;
    bool operator <= ( Mare& ) ;
    void operator = ( int ) ;
    void operator = ( char* ) ;
    void afis ( void ) ;
} ;

Mare :: Mare () { // A = 0
    this -> resize ( 20 ) ;
}

Mare Mare :: operator + ( Mare &B ) {
    int i, t = 0;
    Mare C ;

    for ( i = 1; i <= A[0] || i <= B[0] || t; ++i, t /= 10 ) {
        C[i] = ( t += verf ( A, i ) + verf ( B, i ) ) % 10 ;
    }

    C[0] = i - 1;

    return C ;
}

bool Mare :: operator <= ( Mare &B ) {
    if ( A[0] < B[0] ) return true;
    else if ( A[0] > B[0] ) return false;

    for ( int i = A[0]; i > 0; --i )
        if ( A[i] < B[i] ) return true;
        else if ( A[i] > B[i] ) return false;

    return true;
}

Mare Mare :: operator * ( Mare &B ) {
    int i, j, t ;
    Mare C ;
    for ( i = 1; i <= A[0]; ++i ) {
        for (t = 0, j = 1; j <= B[0] || t; j++, t /= 10)
            C[i + j - 1] = ( t += C[i + j - 1] + verf ( A, i ) * verf ( B, j ) ) % 10;
        if ( i + j - 2 > C[0] )
            C[0] = i + j - 2;
    }

    return C ;
}

void Mare :: operator += ( Mare &B ) {
    int i, t = 0;

    for ( i = 1; i <= A[0] || i <= B[0] || t; ++i, t /= 10 ) {
        A[i] = ( t += verf ( A, i ) + verf ( B, i ) ) % 10 ;
    }

    A[0] = i - 1;
}

void Mare :: operator = ( int X ) {
    for ( A[0] = 0; X ; X /= 10 ) {
        A[ ++A[0] ] = X % 10 ;
    }
}

void Mare :: operator = ( char *B ) {
    A[0] = strlen ( B ) ;

    for ( int i = A[0]; i ; --i )
        A[i] = B[A[0] - i] - '0';
}

void Mare :: afis ( void ) {
    for ( int i = A[0]; i ; --i ) {
        printf ( "%d", A[i] ) ;
    }
    printf ( "\n" ) ;
}

int n,d,i,g=0,nw=1,aux,j,k;
char a1[100], b1[100] ;
Mare a,b;
Mare cp[1001][1001],cf[2][1001],sum;

int main ( void ) {
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;
    scanf("%d %d %s %s",&n,&d,a1,b1);
    a = a1, b = b1 ;
    cp[1][0]=1;
    cp[1][1]=1;
    cp[0][1]=0;
    cp[0][0]=1;
    for(i=2; i<=n; i++)
        for(j=1; j<i; j++) {
            cp[i][j]=cp[i-1][j]+cp[i-1][j-1];
            cp[i][i]=1;
            cp[i][0]=1;
        }
    for(i=0; i<=n; i++)
        cf[0][i]=0;
    for(j=2; j<=n; j++,nw ^= 1) {
        sum=0;
        for(i=j; i<=n; i++) {
            cf[nw][i]=0;
            for(k=j-1; k<i-d; k++)
                cf[nw][i]+=cf[nw ^ 1][k];
            for(k=max(i-d,j-1); k<i; k++)
                cf[nw][i]+=cp[k-1][j-2];
            sum+=cf[nw][i];
            Mare aux ;
            aux = sum * b ;
            if(cp[n][j]*a<=aux) {
                g=1;
                printf("%d",j);
                break;
            }
        }
        if(g==1) break;
    }
}