369 - Combinations

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mhm
New poster
Posts: 1
Joined: Sun Mar 14, 2010 12:59 pm

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

Post by mhm » Sun Mar 14, 2010 1:10 pm

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

gtcoder
New poster
Posts: 12
Joined: Tue Mar 23, 2010 5:45 am

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

Post by gtcoder » Mon Mar 29, 2010 9:41 am

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

jhosimar3001
New poster
Posts: 3
Joined: Sun Mar 07, 2010 1:56 am

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

Post by jhosimar3001 » Fri May 14, 2010 4:45 am

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"

jfvs
New poster
Posts: 12
Joined: Wed Feb 02, 2011 10:40 am

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

Post by jfvs » Wed Feb 02, 2011 10:44 am

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
New poster
Posts: 1
Joined: Fri Feb 08, 2013 3:51 pm

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

Post by Marat Usupov » Fri Feb 08, 2013 3:57 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Fri Feb 08, 2013 8:41 pm

Input:

Code: Select all

20 15
0 0
AC output:

Code: Select all

20 things taken 15 at a time is 15504 exactly.
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

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

Post by shuvokr » Wed Jul 17, 2013 2:37 am

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

Code: Select all

enjoying life ..... 

gautamzero
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

Re: 369 - Combinations

Post by gautamzero » Fri Dec 19, 2014 10:22 pm

getting WA :(
why??

Code: Select all

AC
Last edited by gautamzero on Sun Dec 21, 2014 9:26 am, edited 1 time in total.
None but a fool is always right..
so don't be upset when u r wrong..

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 369 - Combinations

Post by lighted » Sun Dec 21, 2014 9:07 am

A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 369 - Combinations

Post by bgcsaif » Sun May 10, 2015 4:04 am

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
New poster
Posts: 5
Joined: Sat Apr 25, 2015 4:00 pm

Re: 369 - Combinations

Post by quanghm » Tue May 12, 2015 10:40 pm

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

msl123
New poster
Posts: 2
Joined: Fri May 22, 2015 7:54 am

Re: 369 - Combinations

Post by msl123 » Fri May 22, 2015 9:09 am

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

Post Reply

Return to “Volume 3 (300-399)”