Cod sursa(job #370986)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 2 decembrie 2009 22:19:51
Problema Bile2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "bile2.in"
#define file_out "bile2.out"

#define Baza 10000
#define Nmax 1020

char s[Nmax];
int comb[2][Nmax][Nmax/10];
int c[2][Nmax][Nmax/10];
int a[Nmax];
int b[Nmax];
int s1[Nmax];
int s2[Nmax];
//long long comb[1001][1001],a,b,c[1001][1001];
int n,d;

void add(int A[], int B[])
{
      int i, t = 0;
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=Baza)
              A[i] = (t += A[i] + B[i]) % Baza;
      A[0]=i-1;
}

void mul(int A[], int B)
{
      int i, t = 0;
      for (i = 1; i <= A[0] || t; i++, t /= Baza)
              A[i] = (t += A[i] * B) % Baza;
      A[0] = i - 1;
}

void Mul(int A[], int B[])
{
      int i, j, t, C[Nmax];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=Baza)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%Baza;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}

void sub(int A[], int B[])
{
      int i, t = 0;
      for (i = 1; i <= A[0]; i++)
              A[i] += (t = (A[i] -= B[i] + t) < 0) * Baza;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

void div(int A[], int B)
{
      int i, t = 0;
      for (i = A[0]; i > 0; i--, t %= B)
              A[i] = (t = t * Baza+ A[i]) / B;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

int cmp(int A[], int B[])
{
    int i;

    if (A[0]!=B[0]) 
		return A[0]<B[0];
    for (i=A[0];i>0;--i)
        if (A[i]!=B[i]) 
			return A[i]<B[i];
    return 0;
}

void init(int A[], int B)
{
	while(B)
	{
		A[++A[0]]=B%Baza;
		B/=Baza;
	}
}


int main()
{
	int i,j,t,ind,stp;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d\n", &n, &d);
	gets(s);
	for (i=strlen(s)-1;i>=0;i-=4)
    {
        for (t=0,j=i-3;j<=i;++j)
            if (j>=0) 
				t=t*10+s[j]-'0';
        a[++a[0]]=t;
    }
	gets(s);
	for (i=strlen(s)-1;i>=0;i-=4)
    {
        for (t=0,j=i-3;j<=i;++j)
            if (j>=0) 
				t=t*10+s[j]-'0';
        b[++b[0]]=t;
    }

	
	//merg cu comb
	init(comb[0][0],1);
	
	ind=1;
	for (i=1;i<=n;++i)
	{
		memset(comb[ind],0,sizeof(comb[ind]));
	    init(comb[ind][0],1);
		for (j=1;j<=n;++j)
		{
			add(comb[ind][j],comb[ind^1][j-1]);
			add(comb[ind][j],comb[ind^1][j]);
		}
	}		
	
	stp=0;
    ind=1;
	//merg cu c
	init(c[0][0],1);
	
    for (i=1;i<=n;++i)
	{
		memset(c[ind],0,sizeof(c[ind]));
		init(c[ind][i],1);
		for (j=1;j<=n;++j)
		{
			add(c[ind][j],c[ind^1][j-1]);
			add(c[ind][j],c[ind^1][max(j-d-1,0)]);
		}
		
		//if (comb[n][i]*(b-a)>=b*c[i][n])

		memcpy(s1,comb[stp][i],sizeof(s1));
		sub(b,a);
		Mul(s1,b);
		memcpy(s2,comb[stp][n],sizeof(s2));
		Mul(s2,b);
		
		if (cmp(s1,s2)>=0)
		{
			printf("%d\n", i);
			break;
		}
	}

			
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}