530 - Binomial Showdown

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
roni
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Location: SUST, BANGLADESH
Contact:

530

Post by 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.
roni(SUST)

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

530...method

Post by Rocky »

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

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

530 - BINOMIAL SHOWDOWN - WA

Post by 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...
fahim
#include <smile.h>

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by 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.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

wow wow wow!
thanks a lot ayon! thanks a lot!
fahim
#include <smile.h>

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

Post by 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
New poster
Posts: 6
Joined: Sun Jun 20, 2004 5:08 pm

Post by 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
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm

530

Post by 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
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm

530 help pls.......

Post by 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
New poster
Posts: 2
Joined: Mon Aug 28, 2006 10:01 pm
Location: Jakarta, Indonesia

530 - Runtime Error... need i/o samples

Post by 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
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

530 why compile error :(

Post by Spykaj »

Code: Select all

Cut... I have acc :]

hf_1992
New poster
Posts: 4
Joined: Sat Nov 11, 2006 6:44 am

530 WA*3 and RE*2

Post by 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
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

rvarshne
New poster
Posts: 3
Joined: Tue Dec 05, 2006 11:02 pm

Wrong Answer for 530

Post by 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);
			   }
		 }
}

Post Reply

Return to “Volume 5 (500-599)”