369 - Combinations

[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.
Thanks a lot

[gtcoder]

@aliahmed
Just don't reset k for k>=(n/2). It works.

[jhosimar3001]

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"

[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

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

[brianfry713]

Input:

Code: Select all

20 15
0 0

AC output:

Code: Select all

20 things taken 15 at a time is 15504 exactly.

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

[gautamzero]

getting WA
why??

Code: Select all

AC

[lighted]

Check input here. http://www.udebug.com/UVa/369

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

[quanghm]

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

[msl123]

Have submited six, not AC yet...
A little later, maybe i should see how other guys write it