## 530 - Binomial Showdown

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Thanks

Thank you I got Acc......
try_try_try_try_&&&_try@try.com
This may be the address of success.

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
now i got RE..and most of the cases gives the right answers..And i thought my arithmetic seem no mistakes..I used it and got AC in 369 before..My arithmetic is to calculate the number of the emement of factorial..But it may crash in this case: 9111 1;It will give the wrong answers..i can't find what mistake i have made..i 've confused..help..thanks in advance~

Code: Select all

``````#include <iostream.h>
#include "math.h"

typedef struct
{
int prime;
int num;
}Prime;

bool IfPrime (int n)
{
int limit;

if (n == 2)
return true;
if (n % 2 == 0)
return false;

limit = sqrt (n) + 1;

for (int i = 3; i < limit; i = i + 2)
if (n % i == 0)
return false;
return true;
}

int main ()
{
int n, m;
int i, j, temp;
long long result;
Prime p[6544];
int pNum = 0;

for (i = 0; i <= 65536; i++)
if (IfPrime (i))
p[pNum++].prime = i;

while (cin>>n>>m && n||m)
{
result = 1;
for (i = 1; i < 6544; i++)
p[i].num = 0;

for (i = 2; i <= n; i++)
{
temp = i;

for (j = 1; temp != 1; j++)
{
while (temp % p[j].prime == 0)
{
p[j].num++;
temp = temp / p[j].prime;
}
}
}

for (i = 2; i <= m; i++)
{
temp = i;

for (j = 1; temp != 1; j++)
{
while (temp % p[j].prime == 0)
{
p[j].num--;
temp = temp / p[j].prime;
}
}
}

for (i = 2; i <= n - m; i++)
{
temp = i;

for (j = 1; temp != 1; j++)
{
while (temp % p[j].prime == 0)
{
p[j].num--;
temp = temp / p[j].prime;
}
}
}

for (i = 1; i < 26; i++)
{
for (j = 0; j < p[i].num; j++)
result *= p[i].prime;
}

cout<<result<<endl;
}
return 0;
}``````
[/quote]

New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm
my method

test case

Code: Select all

``````110 6
``````

Code: Select all

``````110 * 109 * 108 * 107 * 106 * 105
-------------------------------------------
6 * 5 * 4 * 3 * 2 * 1
``````
you can use 2 matrix or vector to produce them

2.run O(n2) loop to "reduce a fraction" (calculate gcd)

3.the final answer is multiple numerator.

KRUNCH
New poster
Posts: 8
Joined: Sun May 18, 2008 1:03 pm

### Re: 530 woes

On this problem i got RE

Code: Select all

``````#include <iostream>
#include <vector>

using namespace std;

int gcd (int u, int v)
{
int t;
while (u>0)
{
if (u<v) {t=u;u=v;v=t;}
u=u-v;
}
return v;
}

int main ()
{
long long double n,m,r,h;
bool first=true;
vector <int> n1,m1;
while (cin>>n>>m)
{
if (n==0 && m==0) break;
if (!first) cout<<endl; else first=false;
r=1;
n1.clear();
m1.clear();
for (int i=n-m+1;i<n+1;i++)
{n1.push_back(i);}
for (int i=2;i<m+1;i++)
{m1.push_back(i);}
for (int i=0;i<n1.size();i++)
{
for (int j=0;j<m1.size();j++)
{
h=gcd(n1[i],m1[j]);
if (n1[i]>1 && m1[j]>1 && h>1)
{
n1[i]/=h;m1[j]/=h;
}
}
}
for (int i=0;i<n1.size();i++) {r*=n1[i];}
cout<<r<<endl;
}
return 0;
}

``````
And can some one say me why do i get WA at 369 because of this. the code is the same except the
cout<<r<<endl; being cout<<n<<" things taken "<<m<<" at a time is "<<r<<" exactly.";

wallace
New poster
Posts: 10
Joined: Thu Feb 26, 2009 4:03 pm

### Re: 530 woes

I'm trying to make the 530, but i get wa!
this is my code
thank you

Code: Select all

``````
#include<iostream>

using namespace std;

int main()
{
int n,m,maior;
long long c;

cin >> n >> m;

while( n != 0 && m != 0)
{
c = 0;
maior = max(m,n-m);

{
}

cout << n <<" things taken "<< m << " at a time is " << (long long)res << " exactly."<< endl;
cin >> n >> m;

}
return 0;
}

``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 530 woes

Your code looks like the code of problem 369 not 530

sudipta
New poster
Posts: 11
Joined: Wed Sep 30, 2009 7:23 pm
Location: Sylhet

### I need Help on 530(Binomial Showdown)

I submitted this code. But got WA. Con u help me?
#include<stdio.h>
long double fact(long double n)
{
if (n==0) return 1;
else return (n*fact(n-1));
}

int main()
{
long double n,k,r,f,g,temp;
while(scanf("%Lf%Lf",&n,&k)==2)
{
long double u=1,l1=1,l2=1;
if(n==0 && k==0) break;

f=fact(n);
r=fact(k)*fact(n-k);
g=f/r;
printf("%.0Lf\n",g);
}
return 0;
}
Don't Copy, Think Also

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: I need Help on 530(Binomial Showdown)

i think there is precision error
So you should use integer operation only

like nCr= n!/(r!* (n-r)!)

n *( n-1)* (n-2)* ...... (n-r+1)* (n-r)* (n-r-1)* ..........3*.2*1
-------------------------------------------------------------------
{r*( r-1)*(r-2).........3.2.1 )} {(n-r)* (n-r-1)...........3*2*1}

n* (n-1)*(n-2)*.............(n-r+1)
---------------------------------------
r*(r-1)*(r-2)*...............3*2*1

let
10 5
so
10*9*8*...............(10-5+1)
-----------------------------------
5 *4*..............2*1

10*9*8*7*6
------------
5*4*3*2*1

You should use gcd between successive Numerator and denominator

Hopes it helps you
Try to catch fish rather than asking for some fishes.

sudipta
New poster
Posts: 11
Joined: Wed Sep 30, 2009 7:23 pm
Location: Sylhet

### Re: I need Help on 530(Binomial Showdown)

Thank you very much.
I got it.
Don't Copy, Think Also

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: I need Help on 530(Binomial Showdown)

what is this ?
Try to catch fish rather than asking for some fishes.

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

### Re: 530 woes

Code: Select all

``````#include<iostream>
#include<stdio.h>
using namespace std;

int main()
{
long double y,d,k,n;

while((scanf("%lf %lf",&n,&k))==2 && n>=1&& k>=0 && k<=n)
{

d=1;
for( y=0;y<=k-1;y++)
d*=(n-y)/(k-y);

printf("%.lf\n",d);
}
return 0;
}
``````

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

### 530 Why WA

why im getting wrong answer...plz hlp me.... i have got AC in 369 no problem.

Code: Select all

``````#include<iostream>
using namespace std;

int main()
{
long double y,d,k,n;
while((scanf("%lf %lf",&n,&k))==2 && n>=1&& k>=0 && k<=n)
{
d=1;
for( y=0;y<=k-1;y++)
d*=(n-y)/(k-y);
printf("%.lf\n",d);
}
return 0;
}``````

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 530 woes

You are using "long double" as data type.
But you are printing :-

Code: Select all

``printf("%.lf\n",d);``
I think this should be changed to:-

Code: Select all

``printf("%.llf\n",d);``
And i think this won't be enough to solve this problem
try_try_try_try_&&&_try@try.com
This may be the address of success.

Snakib
New poster
Posts: 7
Joined: Mon May 31, 2010 6:25 am

### Re: 530 woes

i am facing time limit error
#include<stdio.h>
double a(int b)
{
int c,e=1;
for(c=1;c<=b;c++)
{
e=e*c;
}
return e;
}

int main()
{
int b,n,r,j=0,d,ans[23];
double e[3];

while(n!=0,r!=0)
{
scanf("%d%d",&n,&r);

if(n==0 && r==0)
break;a
e[0]=a(n);
e[1]=a(r);
e[2]=a(n-r);
ans[j]=e[0]/(e[1]*e[2]);
j++;
}

for(d=0;d<j;d++)
printf("%d\n",ans[d]);
return 0;
}

Snakib
New poster
Posts: 7
Joined: Mon May 31, 2010 6:25 am

### Re: 530 woes

[code#include<stdio.h>
double a(int b)
{
int c,e=1;
for(c=1;c<=b;c++)
{
e=e*c;
}
return e;
}

int main()
{
int b,n,r,j=0,d,ans[23];
double e[3];

while(n!=0,r!=0)
{
scanf("%d%d",&n,&r);

if(n==0 && r==0)
break;a
e[0]=a(n);
e[1]=a(r);
e[2]=a(n-r);
ans[j]=e[0]/(e[1]*e[2]);
j++;
}

for(d=0;d<j;d++)
printf("%d\n",ans[d]);
return 0;
}
]