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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Thanks

Post by Obaida » Wed Jan 30, 2008 6:06 am

:wink: Thank you I got Acc...... :lol:
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

Post by AcmNightivy » Sun Feb 10, 2008 6:28 pm

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]

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

Post by deadangelx » Tue Mar 11, 2008 1:28 pm

my method

test case

Code: Select all

110 6
1.answer equals

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

Post by KRUNCH » Wed Nov 05, 2008 12:16 pm

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

Post by wallace » Sat May 02, 2009 12:58 am

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;
 double numerador,denominador, res;
 long long c;
 
 cin >> n >> m;
 
 while( n != 0 && m != 0)
 {
   numerador = denominador = res =1;
   c = 0;
   maior = max(m,n-m);
  
   for(numerador = n, denominador = n - maior; numerador > maior; numerador--,denominador--)
    {
      res = res * (numerador/denominador);
    }
    
    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

Post by helloneo » Sat May 02, 2009 5:54 am

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)

Post by sudipta » Thu Oct 01, 2009 8:35 am

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)

Post by arifcsecu » Sat Oct 03, 2009 8:51 pm

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 desired answer


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)

Post by sudipta » Sun Oct 04, 2009 11:55 am

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)

Post by arifcsecu » Fri Nov 13, 2009 3:21 pm

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

Post by Eather » Mon Feb 01, 2010 10:36 am

my code is below... i dont know why im getting wrong answer... could anyone please help me to find out....??? :(

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

Post by Eather » Fri Feb 12, 2010 6:42 am

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 530 woes

Post by Obaida » Tue Feb 23, 2010 6:53 am

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

Post by Snakib » Mon May 31, 2010 6:28 am

can anyone help me please
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

Post by Snakib » Mon May 31, 2010 12:52 pm

[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;
}
]

Post Reply

Return to “Volume 5 (500-599)”