Page 7 of 7

369 / 530 : Combinations : WAs all the way,Please Help

Posted: Sun Mar 14, 2010 1:10 pm
by mhm
Here's my C code :

Code: Select all

#include<stdio.h>

long long int combinFnc(short int n,short int m) {
long long int finalVal=1;
short int multList[51]={0},divList[51]={0};
register short int i,j,k=0;

for(i=(n-m)>m?(n-m+1):m+1,j=(n-m)>m?m:(n-m);(i<=n || j>=2);i++,j--,k++) {
if(i<=n)
multList[k]=i;
if(j>=2)
divList[k]=j;
}

/*beginDebug
for(i=0;divList[i]!=0;i++)
printf("*%hd*\n",divList[i]);
endDebug */


for(i=0;divList[i]!=0;i++) {
for(j=0;multList[j]!=0;j++) {
if((multList[j]%divList[i])==0){
multList[j]/=divList[i];
break;
}
}
}

for(i=0;multList[i]!=0;i++)
finalVal*=multList[i];


return finalVal;
}

int main() {
short int n,m;
while(1) {
scanf("%hd %hd",&n,&m);
if(n==0 && m==0)
break;
else
printf("%hd things taken %hd at a time is %lld exactly.",n,m,combinFnc(n,m));
}
return 0;
}
I have tried all test sets I could find.
I get WA everytime with 0.008 second runtime.
Same thing happens in 530 (i tried that with different output formatting)
Somebody Please HELP. :oops:
Thanks a lot

Re: 369 WA even if it works for every test case i found :S

Posted: Mon Mar 29, 2010 9:41 am
by gtcoder
@aliahmed
Just don't reset k for k>=(n/2). It works.

Re: 369 / 530 : Combinations : WAs all the way,Please Help

Posted: Fri May 14, 2010 4:45 am
by jhosimar3001
mhm wrote:Here's my C code :

Code: Select all

printf("%hd things taken %hd at a time is %lld exactly.",n,m,combinFnc(n,m));
Afters "exactly." you must print end of line --> "\n"

Re: 369 / 530 : Combinations : WAs all the way,Please Help

Posted: Wed Feb 02, 2011 10:44 am
by jfvs
I dont know if you have got AC yet, but you have an error on your algorithm in the combinFnc function. Check this part

Code: Select all

for(i=0;divList[i]!=0;i++) {
for(j=0;multList[j]!=0;j++) {
if((multList[j]%divList[i])==0){
multList[j]/=divList[i];
break;
}
}
}
Is where your error is, the calculation is wrong for some combinations... try these imputs:

100 100
100 99
100 98
100 97
100 96
100 95
100 94
100 93
100 92
100 91
100 90
100 89
100 88
100 87
100 86
100 85
100 84
100 83
100 82
100 81
100 80

PS: sorry for my bad english

Re: 369 / 530 : Combinations : WAs all the way,Please Help

Posted: Fri Feb 08, 2013 3:57 pm
by Marat Usupov
Hi! I can understand why I am getting wrong answer in this. Problem no. 369

Code: Select all

#include <iostream>

using namespace std;

#define i64 unsigned long long int

i64 dp[100][100];

i64 nCr(int n, int r)
{
    if(r==n) return dp[n][r] = 1;
    else if(r==0) return dp[n][r] = 1;
    else if(r==1) return dp[n][r] = (i64)n;
    else if(dp[n][r]) return dp[n][r];

    return dp[n][r] = nCr(n-1, r) + nCr(n-1,r-1);
}

int main()
{
    int n,r ;

    while(cin>>n>>r && (n||r))
    {
        if(n==0&&r==0) break;
        r = (r<n-r)? r : n-r;
        cout<<n<<" things taken "<<r<<" at a time is "<<nCr(n,r)<<" exactly."<<endl;
    }
    return 0;
}

Re: 369 / 530 : Combinations : WAs all the way,Please Help

Posted: Fri Feb 08, 2013 8:41 pm
by brianfry713
Input:

Code: Select all

20 15
0 0
AC output:

Code: Select all

20 things taken 15 at a time is 15504 exactly.

Re: 369 / 530 : Combinations : WAs all the way,Please Help

Posted: Wed Jul 17, 2013 2:37 am
by shuvokr
For this problem who got WA

You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long.

:P

Re: 369 - Combinations

Posted: Fri Dec 19, 2014 10:22 pm
by gautamzero
getting WA :(
why??

Code: Select all

AC

Re: 369 - Combinations

Posted: Sun Dec 21, 2014 9:07 am
by lighted

Re: 369 - Combinations

Posted: Sun May 10, 2015 4:04 am
by bgcsaif
Getting WA! Tried some inputs.... It works fine....
:-(

Code: Select all

#include <stdio.h>
int main()
{
	long long int n, m, i, j, a, c, s, s2, k;
	while (scanf("%lld %lld", &n, &m) == 2)
	{
		if (n == 0 && m == 0)
			break;
		k = m;
		a = n - m;
		if (a < m)
		{
			c = a;
			a = m;
			m = c;
		}
		a = a + 1, s = 1, s2 = 1;
		while (a <= n)
		{
			s *= a;
			a++;
		}
		while (m > 0)
		{
			s2 *= m;
			m--;
		}
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, k,
			   s / s2);
	}
}

Re: 369 - Combinations

Posted: Tue May 12, 2015 10:40 pm
by quanghm
bgcsaif wrote:Getting WA! Tried some inputs.... It works fine....
:-(
You tries to compute n(n-1)...(n-m+1). That's too much for long long. Try input:
100 10
100 15
0 0

Re: 369 - Combinations

Posted: Fri May 22, 2015 9:09 am
by msl123
Have submited six, not AC yet... :(
A little later, maybe i should see how other guys write it :-?