## 369 - Combinations

Moderator: Board moderators

mhm
New poster
Posts: 1
Joined: Sun Mar 14, 2010 12:59 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)
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

@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

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

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

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

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

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.

Code: Select all

``enjoying life ..... ``

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

### Re: 369 - Combinations

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

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

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

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

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