Cod sursa(job #2042317)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 18 octombrie 2017 13:49:33
Problema Bile2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>

FILE *fin = fopen("bile2.in", "r");
FILE *fout = fopen("bile2.out", "w");

#define MAXN 1000

int a, b;
long long comb;
long long d[2][MAXN + 1];

int main() {
    int n, e;
    fscanf(fin, "%d%d", &n, &e);
    e++;

    fscanf(fin, "%d%d", &a, &b);
    a = b - a;

    int k = 1;
    comb = n;
    d[1][1] = 1;
    for (int i = 2; i <= n; i++)
        d[1][i] = d[1][i - 1] + 1;

    while (d[k % 2][n] * b > comb * a) {
        comb *= n - k;
        k++;
        comb /= k;

        d[k % 2][k - 1] = d[k % 2][k - 2] = 0;
        for (int i = k; i <= n; i++) {
            d[k % 2][i] = d[k % 2][i - 1];
            if (i > e)
                d[k % 2][i] += d[(k - 1) % 2][i - e];
        }
    }

    fprintf(fout, "%d\n", k);

    fclose(fin);
    fclose(fout);
    return 0;
}