Cod sursa(job #2240889)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 14 septembrie 2018 12:54:58
Problema Bile2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<bits/stdc++.h>
using namespace std;
int n,d,a,b;
long long dp[2][1005];
long long c=1LL;
int k=1;

int main()
{
    freopen("bile2.in","r",stdin);
    freopen("bile2.out","w",stdout);


    scanf("%d%d",&n,&d);

    /**
        dp[i][j]-i bile extrase, in ordine crescatoare, ultima bila<=j
        dp[i][j]<-dp[i-1][j]+dp[i-1][j-d-1]
    **/


    scanf("%d",&a);
    scanf("%d",&b);

    a=b-a;
    c=1LL*n;

    dp[1][1]=1;

    for(int i=2;i<=n;i++)
    {
        dp[1][i]=dp[1][i-1]+1;
    }

    while((dp[k%2][n]*b)>(c*a))
    {
        c=c*(n-k);
        k++;
        c/=k;
        dp[k%2][k-1]=dp[k%2][k-2]=0;
        for(int i=k;i<=n;i++)
        {
            dp[k%2][i]=dp[k%2][i-1];
            if(i>(d+1))
            {
                dp[k%2][i]+=dp[(k-1)%2][i-d-1];
            }
        }
    }


    printf("%d\n",k);





    return 0;
}