## 369 - Combinations

**Moderator:** Board moderators

c = 1;

for (i=N,j=1;j<=R;i--,j++)

c=(c*i)/j;

Here, R is the minimum of M or N-M.

And the type of c is double or long long. All other variables are int.

It can also be solved by using c as an int. In that case, first divide c and j by gcd(c,j). Suppose the new value of c and j is c' and j'. Now divide i and j' by gcd(i, j'). Let the new value of i and j' is i' and j''. Then the answer will be c' * i'. [You need not do this in all iteration. It only requires at the last iteration (i.e when j=R).]

### 369 (combinations) - how to?!

Hi everyone!

I'm trying to solve the problem #369, but I don't know how to do it... I have a library with functions to manipulate big integers and I was trying to do the factorials in the ordinary way, i.e, multiplying... I don't know if i'm having some overflow problem or not, but my problem is into an infinity loop I guess...

Is there any easier way to solve this problem? Just a clue, please!

Thanks!

I'm trying to solve the problem #369, but I don't know how to do it... I have a library with functions to manipulate big integers and I was trying to do the factorials in the ordinary way, i.e, multiplying... I don't know if i'm having some overflow problem or not, but my problem is into an infinity loop I guess...

Is there any easier way to solve this problem? Just a clue, please!

Thanks!

The problem says that :

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

so a simple technique will pass this problem.

input :

100 6

Code: Select all

```
100!
= ------------
(100-6)!*6!
100!
= ------------
94! * 6!
94! * 95 * 96 * 97 * 98 * 100
= ----------------------------------
94! * 6!
(eliminate 94!)
95*96*97*98*99*100
= --------------------
2*3*4*5*6
(divide 96 with 2*6 = 8)
(divide 99 with 3 = 33)
(divide 100 with 4*5 = 5)
= 95 * 8 * 97 * 98 * 33 * 5
= 1192052400
```

"Life is beautiful with algorithm"

### Almost there... :(

This thing is driving me mad... This should be a simple task, but I don't know how....

Well, the problem is: How to choose the right numbers to use (and how to keep track of them) to simplify the fraction?

My code works for the test cases given in the problem, but i'm getting WA anyway. I think the numbers aren't fitting into long long int. I need to find the right order to simplify the fraction!

My code follows.... Take a look please!!

Well, the problem is: How to choose the right numbers to use (and how to keep track of them) to simplify the fraction?

My code works for the test cases given in the problem, but i'm getting WA anyway. I think the numbers aren't fitting into long long int. I need to find the right order to simplify the fraction!

My code follows.... Take a look please!!

Code: Select all

```
#include <iostream>
using namespace std;
void simplify(unsigned long long int *n, unsigned long long int *m)
{
for(int i = 100; i >= 2; i--)
{
if(*n%i == 0 && *m%i == 0)
{
*n = *n/i;
*m = *m/i;
}
}
}
int main()
{
unsigned long long int num, den, C;
unsigned long long int n, m, i, j;
while(true)
{
cin>>n>>m;
if(n == 0 && m == 0) break;
num = n-m+1;
den = m;
i = num+1;
j = den-1;
while(i <= n && j > 1)
{
unsigned long long int aux1 = i;
unsigned long long int aux2 = j;
simplify(&aux1, &aux2);
num *= aux1;
den *= aux2;
i++;
j--;
}
while(i <= n)
{
num *= i;
i++;
}
while(j > 1)
{
den *= j;
j--;
}
if(num != 0 && den != 0)
C = num/den;
else C = 0;
cout<<n<<" things taken "<<m<<" at a time is "<<C<<" exactly."<<endl;
}
return 0;
}
```

You can just use the identity: C(n,m) = C(n,m-1)*(n-m+1)/mIs there any easier way to solve this problem?

Starting from C(n,0)=1, repeatedly apply the formula until you reach C(n,m).

With this formula, in the worst case you'll need to work with numbers of order 100*2^31, which fit well in 'long long'.

mf wrote:You can just use the identity: C(n,m) = C(n,m-1)*(n-m+1)/mIs there any easier way to solve this problem?

Starting from C(n,0)=1, repeatedly apply the formula until you reach C(n,m).

With this formula, in the worst case you'll need to work with numbers of order 100*2^31, which fit well in 'long long'.

So, why this

Code: Select all

```
procedure solve;
var
n, m, i: integer;
a: int64;
begin
while true do begin
readln(n,m);
if (n=0) and (m=0) then break;
a:= n;
for i:=2 to m do
a:= (a*int64(n-i+1)) div i;
writeln(n,' things taken ',m,' at a time is ',a,' exactly.');
end;
end;
```

- little joey
- Guru
**Posts:**1080**Joined:**Thu Dec 19, 2002 7:37 pm

If you calculate say C(100,94), which is 1192052400 and fits into a standard integer, you pass the 'monster' C(100,50), which is about 10^29 and doesn't fit into even an int64.kp wrote: So, why thisgives WA???Code: Select all

`procedure solve; var n, m, i: integer; a: int64; begin while true do begin readln(n,m); if (n=0) and (m=0) then break; a:= n; for i:=2 to m do a:= (a*int64(n-i+1)) div i; writeln(n,' things taken ',m,' at a time is ',a,' exactly.'); end; end;`

Use a well known identity and approach such problems 'from the other side'.

The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Thanks,little joey wrote:

If you calculate say C(100,94), which is 1192052400 and fits into a standard integer, you pass the 'monster' C(100,50), which is about 10^29 and doesn't fit into even an int64.

Use a well known identity and approach such problems 'from the other side'.

I really should think twice before posting such silly questions.

(intput)

100 90

100 50

99 40

100 6

20 5

18 6

0 0

(output)

1591253560

445776180

445776180

1192052400

15504

18564

(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT) [/quote]

I have a problem !

I used calculator to count c(100,90) and c(100,50).

I found that c(100,90) < c(100,50) , but your output

1591253560 > 445776180.

Though I got AC , my ans are c(100,90)=1591253560 and

c(100,50)=-938977944.

why mine is different from yours??

(intput)

100 90

100 50

99 40

100 6

20 5

18 6

0 0

(output)

1591253560

445776180

445776180

1192052400

15504

18564

(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT) [/quote]

I have a problem !

I used calculator to count c(100,90) and c(100,50).

I found that c(100,90) < c(100,50) , but your output

1591253560 > 445776180.

Though I got AC , my outputs were c(100,90)=1591253560 and

c(100,50)=-938977944.

why mine is different from yours??

Well, it's just because the online judge does not use large test cases..joebin wrote:[CORRECT!!]

(intput)

100 90

100 50

99 40

100 6

20 5

18 6

0 0

(output)

1591253560

445776180

445776180

1192052400

15504

18564

(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT)

In fact, C(100, 50) = 8247740487481686900760421832

(You can try it using the windows calculator)

which can not be correctly held using a LONG LONG UNSIGNED

↓It seems contradictory to the original question...

Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large.

### WA... need help

I don't know wjy my program WA... i'm really confuse..... somebody help plzzz...........

#include<cstdio>

#include<cstdlib>

int main()

{

long int N, M, C, i, j;

while(scanf("%ld %ld",&N,&M)==2)

{

if(N==0&&M==0) break;

else

{

if(N-M < M) M=N-M;

C=1;

for(i=N,j=1;j<=M;i--,j++)

{

C=(C*i)/j;

}

printf("%ld things taken %ld at a time is %ld exactly.\n",N,M,C);

}

}

return 0;

}

#include<cstdio>

#include<cstdlib>

int main()

{

long int N, M, C, i, j;

while(scanf("%ld %ld",&N,&M)==2)

{

if(N==0&&M==0) break;

else

{

if(N-M < M) M=N-M;

C=1;

for(i=N,j=1;j<=M;i--,j++)

{

C=(C*i)/j;

}

printf("%ld things taken %ld at a time is %ld exactly.\n",N,M,C);

}

}

return 0;

}

Code: Select all

```
34 14
0 0
```

Code: Select all

`34 things taken 14 at a time is 1391975640 exactly.`