Cod sursa(job #1085607)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 17 ianuarie 2014 10:29:28
Problema Bile2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

#define NMAX 507

using namespace std;

int D[NMAX][NMAX][NMAX], C[NMAX][NMAX][NMAX];

void adun(int a[], int b[]){
    int t = 0;
    a[0] = max(a[0], b[0]);
    for(int i = 1; i <= a[0]; ++i){
        a[i] += b[i] + t;
        t = a[i] / 10;
        a[i] %= 10;
    }
    while(t > 0){
        a[++a[0]] = t % 10;
        t /= 10;
    }
}

void scad(int a[], int b[]){
    int t = 0;
    for(int i = 1; i <= a[0]; ++i){
        a[i] -= (b[i] + t);
        if(a[i] < 0)
            t = 1;
        else
            t = 0;
        a[i] += t * 10;
    }
    while(a[a[0]] == 0)
        -- a[0];
}

void prod(int a[], int x){
    int t = 0;
    for(int i = 1; i <= a[0]; ++i){
        a[i] *= x;
        a[i] += t;
        t = a[i] / 10;
        a[i] %= 10;
    }
    while(t > 0){
        a[++a[0]] = t % 10;
        t /= 10;
    }
}

inline int Comp(int a[], int b[]){
    if(a[0] != b[0])
        return a[0] > b[0];
    for(int i = a[0]; i >= 1; --i)
        if(a[i] != b[i])
            return a[i] > b[i];
    return 0;
}

int main(){
    int n, d, a, b;
    freopen("bile2.in", "r", stdin);
    freopen("bile2.out", "w", stdout);
    scanf("%d %d %d %d", &n, &d, &a, &b);
    for(int i = 0; i <= n; ++i)
        D[0][i][0] = D[0][i][1] = 1;
    C[0][0][0] = C[0][0][1] = 1;
    for(int i = 1; i <= n; ++i){
        C[i][0][0] = C[i][0][1] = 1;
        for(int j = 1; j <= n; ++j){

            memcpy(C[i][j], C[i - 1][j], sizeof(C[i][j]));
            adun(C[i][j], C[i - 1][j - 1]);

            memcpy(D[i][j], D[i][j - 1], sizeof(D[i][j - 1]));
            adun(D[i][j], D[i - 1][max(j - d - 1, 0)]);

        }
    }
    int Aux[NMAX], Aux2[NMAX];
    for(int i = 1; i <= n; ++i){

        memset(Aux, 0, sizeof(Aux));
        memcpy(Aux, C[n][i], sizeof(Aux));
        scad(Aux, D[i][n]);
        prod(Aux, b);

        memset(Aux2, 0, sizeof(Aux));
        memcpy(Aux2, C[n][i], sizeof(Aux2));
        prod(Aux2, a);

        if(Comp(Aux, Aux2) == 1){
            printf("%d\n", i);
            return 0;
        }
    }
    return 0;
}