530 - Binomial Showdown

[roni]

i use prime factorization for this problem. Generate upto 66000. Then add and substract power of the primes for multiplication and division. The resulting powers of primes are then multiply for getting ans.

[Rocky]

i think simple divide & multiplication method is suffeicient for this ..

[smilitude]

here goes my code...

Code: Select all

/*
530 binomial showdown 
submission 1 WA
coded at 10:39pm on 13th oct
*/

#include <stdio.h>
#include <math.h>

double gcd(double a, double b) {
	if(b==0) return a;
	else return gcd(b,fmod(a,b));
}

double nCr(double a, double b) {
	double neumerator=1, dinominator=1;
	double i;
	double gcdvalue;

	for(i=1;i<=b;i++) {
		dinominator*=i;
		neumerator*=(a+1-i);
		gcdvalue=gcd(neumerator,dinominator);
		if(gcdvalue!=1) {
			neumerator=neumerator/gcdvalue;
			dinominator=dinominator/gcdvalue;
		}
	}
return neumerator/dinominator;
}

void main() {
	
	double num1,num2;
	double result;


	while(scanf("%lf %lf",&num1, &num2)==2) {
		if (!num1 && !num2) break;
		result=nCr(num1,num2);
		printf("%.0lf\n",result);
	}
}

i will be really helped...

[ayon]

always remember the formula: nCr = nC(n-r)
so include the code:

Code: Select all

if(num2 > num1-num2)
    num2 = num1 - num2;

Hope it helps. and i think there is no necessity of the gcd.

[smilitude]

wow wow wow!
thanks a lot ayon! thanks a lot!

[WRJ]

I had this problem too.
1. C(n,k) = C(n,n-k)
2. My program memorizes C(n,k) for n and k < 1000
3. C(n,0) = 1;
C(n, n) = 1;
C(n,1) = n;
I hope it will help you.

[boyeric]

I believe there is something funny within this problem. i solved the problem in java, by working on the formula (n-m-1)*...*n / m!, but try first to reduce every multiplier in the numerator with each multiplier in the denominator by their gcd (greatest common devisor), such that we can guarantee, after this process is done, the product of denominators is 1, and the product of the numerator is within 2^31.

ok, finally here comes the funny part, the program keep on getting WA again and again. then i change k to be min(k, n-k), and got AC, but shouldn't their results be identical???!!!!

[jainal uddin]

#include<stdio.h>
int main()
{
long long double s1,s2,n,r,i;
while((scanf("%LLf %LLf",&n,&r)) && (n!=0 && r!=0 ))
{
if( r > n-r)
r=n-r;
s1=1;
s2=1;
for(i=1;i<=r;i++)
{
s1*=n;
n--;
s2*=i;

}

printf("%.0LLf\n",s1/s2);
}

return 0;
}

[jainal uddin]

#include<stdio.h>
int main()
{
long long double s1,s2,n,r,i;
while((scanf("%LLf %LLf",&n,&r)) && (n!=0 || r!=0 ))
{
if(n>=r)
{


if(r==0)
printf("1\n");
else
{
if( r > n-r)
r=n-r;
s1=1;
s2=1;
for(i=1;i<=r;i++) {
s1*=n;
n--;
s2*=i;

}

printf("%.0LLf\n",s1/s2);
}
}
}
return 0;
}

[chocoholic]

I've searched past threads for #530 - Binomial Showdown, but still couldn't find what's wrong with my code. Can anyone here help? Thx in advance!

Here's my code:

Code: Select all

#include <stdio.h>

int main()
{
    unsigned long n, k, i,j;
    unsigned long result, factorial[50];
          
    while(scanf("%lu %lu", &n, &k)!=EOF)
    {
        if(n==0)
            break;
        result = 1;
        for(i=0;i<k;i++)
        {
            factorial[i] = n-i;
        }
        for(j=k;j>1;j--)
        {
            for(i=0;i<k;i++)
            {
                if((factorial[i]%j)==0)
                {
                    factorial[i] = factorial[i] / j;
                    break;
                }
            }    
        }
        for(i=0;i<k;i++)
        {
            result = result * factorial[i];
        }
        printf("%lu\n", result);    
    }    
    return 0;
}
 

[Spykaj]

Code: Select all

Cut... I have acc :]

[hf_1992]

Here is my code

Code: Select all

program VolumeV_530;
var n,i:longword;
function factorial(i:longword):real;
begin if i=0 then factorial:=1
else factorial:=i*factorial(i-1)
end;
function numerator(n,i:longword):real;
begin if i=0 then numerator:=1
else numerator:=(n-i+1)*numerator(n,i-1)
end;
function binomialcoefficient(n,i:longword):real;
begin binomialcoefficient:=numerator(n,i)/factorial(i)
end;
begin
repeat
readln(n,i);
if (n=0)and(i=0) then exit;
writeln(binomialcoefficient(n,i):0:0);
until (n=0)and(i=0);
end.

Why I get runtime error? Can anyone help me?

[albet_januar]

don't know how.. why get TLE??
i use this code for 369 n get ACC..

Code: Select all

#include <stdio.h>

int main()
{
	unsigned long long n, m;
	unsigned long long hasil;
	unsigned long long i, j, k;
	unsigned long long pembagi;
	int array[3000];

	while(scanf("%llu %llu", &n, &m)!=EOF)
	{
		if(n==0 && m==0) break;

		for(i=0;i<3000;i++) array[i] = 0;

		i = n - m;
		hasil = 1;
		pembagi = 1;
		for(i=1;i<=m;i++) array[i] = 1;
		for(j=n;j>=n-i+2 ;j--)
		{
			hasil *= j;
			for(k=1;k<=m;k++)
			{
				if(array[k])
				{
					if(hasil%k==0)
					{
						hasil /= k;
						array[k] = 0;
					}
				}
			}

		}

		if(k<m)
			for(k=1;k<=m;k++)
				if(array[k]) pembagi *= k;

		printf("%llu\n", hasil/pembagi);


	}

	return 0;
}

[Jan]

I dont know whether the following input exists or not. But your code returns wrong.

Input:

Code: Select all

3000 3000
0 0

Output:

Code: Select all

1

Hope it helps.

[rvarshne]

Hi,
Could anyone tell me the mistake with this code?
Thanks

Code: Select all

#include <stdio.h>

int main()
{
      int n, m;

      while(scanf("%d", &n) > 0 && scanf("%d", &m) > 0)
      {
          if(n == 0 && m == 0)
          {
                  break;
          }
		  else if(n == m)
		  {
				  printf("1\n");
		  }
		  else if (m == 0)
		  {
				  printf("0\n");
		  }
		  else
		  {
				   int d = n - m;
				   unsigned long long value = 1;
				   if(d > m)
				   {
					   int i, j;
					   for(i = n, j = 1; i >= (d + 1) && j <= m; i--, j++)
					   {
						   if(value % j == 0)
						   {
								   value /= j;
								   value *= i;
						   }
						   else
						   {
								   int temp = i/j;
								   value *= temp;
						   }
					   }
				   }
				   else
				   {
					   int i, j;
					   for(i = n, j = 1; i >= (m + 1) && j <= d; i--, j++)
					   {
						   if(value % j == 0)
						   {
								   value /= j;
								   value *= i;
						   }
						   else
						   {
								   int temp = i/j;
								   value *= temp;
						   }
					   }
				   }

				   printf("%llu\n", value);
			   }
		 }
}