530 - Binomial Showdown

[Obaida]

Thank you I got Acc......

[AcmNightivy]

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]

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]

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]

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]

Your code looks like the code of problem 369 not 530

[sudipta]

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

[arifcsecu]

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

[sudipta]

Thank you very much.
I got it.

[arifcsecu]

what is this ?

[Eather]

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]

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]

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

[Snakib]

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]

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