## 530 - Binomial Showdown

Moderator: Board moderators

roni
New poster
Posts: 11
Joined: Tue Aug 09, 2005 11:57 am
Contact:

### 530

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

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

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
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
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
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;

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

#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.......

#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

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;

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 :(

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

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
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:
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;

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
Contact:
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

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);
}
}
}
``````