369  Combinations
Moderator: Board moderators

 Experienced poster
 Posts: 136
 Joined: Tue Apr 01, 2003 6:59 am
 Location: Jakarta, Indonesia
What compiler do you use?
Is it standard BC 3.1. like mine or gcc that the judge use?
I assume that as long the code right, the output will be correct as well. The judge simply read your code, compile it and compare the result with their test file. So I assume for gcc, your code produces correct output.
Is it standard BC 3.1. like mine or gcc that the judge use?
I assume that as long the code right, the output will be correct as well. The judge simply read your code, compile it and compare the result with their test file. So I assume for gcc, your code produces correct output.
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
In short you don't have to worry about the case 100 20. However, could you tell me how you got those big numbers as output? My program will simply overflow, but still produce an (wrong) answer within the range of a long.You may assume that the final value of C will fit in a 32bit Pascal LongInt or a C long.
INPUT OUTPUT FOR 369
if the result is so large. then last 2 or 3 digits are considerable.
INPUT
100 20
100 90
100 85
88 12
67 12
100 6
23 5
34 20
17 9
98 6
67 21
34 34
12 11
90 6
80 7
70 7
60 8
50 9
45 10
OUTPUT
100 things taken 20 at a time is 535983370403809682000 exactly.
100 things taken 90 at a time is 17310309456440 exactly.
100 things taken 85 at a time is 253338471349988640 exactly.
88 things taken 12 at a time is 205371886988268 exactly.
67 things taken 12 at a time is 5996962277488 exactly.
100 things taken 6 at a time is 1192052400 exactly.
23 things taken 5 at a time is 33649 exactly.
34 things taken 20 at a time is 1391975640 exactly.
17 things taken 9 at a time is 24310 exactly.
98 things taken 6 at a time is 1052618392 exactly.
67 things taken 21 at a time is 129728497393775280 exactly.
34 things taken 34 at a time is 1 exactly.
12 things taken 11 at a time is 12 exactly.
90 things taken 6 at a time is 622614630 exactly.
80 things taken 7 at a time is 3176716400 exactly.
70 things taken 7 at a time is 1198774720 exactly.
60 things taken 8 at a time is 2558620845 exactly.
50 things taken 9 at a time is 2505433700 exactly.
45 things taken 10 at a time is 3190187286 exactly.
INPUT
100 20
100 90
100 85
88 12
67 12
100 6
23 5
34 20
17 9
98 6
67 21
34 34
12 11
90 6
80 7
70 7
60 8
50 9
45 10
OUTPUT
100 things taken 20 at a time is 535983370403809682000 exactly.
100 things taken 90 at a time is 17310309456440 exactly.
100 things taken 85 at a time is 253338471349988640 exactly.
88 things taken 12 at a time is 205371886988268 exactly.
67 things taken 12 at a time is 5996962277488 exactly.
100 things taken 6 at a time is 1192052400 exactly.
23 things taken 5 at a time is 33649 exactly.
34 things taken 20 at a time is 1391975640 exactly.
17 things taken 9 at a time is 24310 exactly.
98 things taken 6 at a time is 1052618392 exactly.
67 things taken 21 at a time is 129728497393775280 exactly.
34 things taken 34 at a time is 1 exactly.
12 things taken 11 at a time is 12 exactly.
90 things taken 6 at a time is 622614630 exactly.
80 things taken 7 at a time is 3176716400 exactly.
70 things taken 7 at a time is 1198774720 exactly.
60 things taken 8 at a time is 2558620845 exactly.
50 things taken 9 at a time is 2505433700 exactly.
45 things taken 10 at a time is 3190187286 exactly.
INPUT OUTPUT FOR 369
if the result is so large. then last 2 or 3 digits are considerable.
INPUT
100 20
100 90
100 85
88 12
67 12
100 6
23 5
34 20
17 9
98 6
67 21
34 34
12 11
90 6
80 7
70 7
60 8
50 9
45 10
OUTPUT
100 things taken 20 at a time is 535983370403809682000 exactly.
100 things taken 90 at a time is 17310309456440 exactly.
100 things taken 85 at a time is 253338471349988640 exactly.
88 things taken 12 at a time is 205371886988268 exactly.
67 things taken 12 at a time is 5996962277488 exactly.
100 things taken 6 at a time is 1192052400 exactly.
23 things taken 5 at a time is 33649 exactly.
34 things taken 20 at a time is 1391975640 exactly.
17 things taken 9 at a time is 24310 exactly.
98 things taken 6 at a time is 1052618392 exactly.
67 things taken 21 at a time is 129728497393775280 exactly.
34 things taken 34 at a time is 1 exactly.
12 things taken 11 at a time is 12 exactly.
90 things taken 6 at a time is 622614630 exactly.
80 things taken 7 at a time is 3176716400 exactly.
70 things taken 7 at a time is 1198774720 exactly.
60 things taken 8 at a time is 2558620845 exactly.
50 things taken 9 at a time is 2505433700 exactly.
45 things taken 10 at a time is 3190187286 exactly.
INPUT
100 20
100 90
100 85
88 12
67 12
100 6
23 5
34 20
17 9
98 6
67 21
34 34
12 11
90 6
80 7
70 7
60 8
50 9
45 10
OUTPUT
100 things taken 20 at a time is 535983370403809682000 exactly.
100 things taken 90 at a time is 17310309456440 exactly.
100 things taken 85 at a time is 253338471349988640 exactly.
88 things taken 12 at a time is 205371886988268 exactly.
67 things taken 12 at a time is 5996962277488 exactly.
100 things taken 6 at a time is 1192052400 exactly.
23 things taken 5 at a time is 33649 exactly.
34 things taken 20 at a time is 1391975640 exactly.
17 things taken 9 at a time is 24310 exactly.
98 things taken 6 at a time is 1052618392 exactly.
67 things taken 21 at a time is 129728497393775280 exactly.
34 things taken 34 at a time is 1 exactly.
12 things taken 11 at a time is 12 exactly.
90 things taken 6 at a time is 622614630 exactly.
80 things taken 7 at a time is 3176716400 exactly.
70 things taken 7 at a time is 1198774720 exactly.
60 things taken 8 at a time is 2558620845 exactly.
50 things taken 9 at a time is 2505433700 exactly.
45 things taken 10 at a time is 3190187286 exactly.
INPUT OUTPUT FOR 369
if the result is so large. then last 2 or 3 digits are considerable.
INPUT
100 20
100 90
100 85
88 12
67 12
100 6
23 5
34 20
17 9
98 6
67 21
34 34
12 11
90 6
80 7
70 7
60 8
50 9
45 10
OUTPUT
100 things taken 20 at a time is 535983370403809682000 exactly.
100 things taken 90 at a time is 17310309456440 exactly.
100 things taken 85 at a time is 253338471349988640 exactly.
88 things taken 12 at a time is 205371886988268 exactly.
67 things taken 12 at a time is 5996962277488 exactly.
100 things taken 6 at a time is 1192052400 exactly.
23 things taken 5 at a time is 33649 exactly.
34 things taken 20 at a time is 1391975640 exactly.
17 things taken 9 at a time is 24310 exactly.
98 things taken 6 at a time is 1052618392 exactly.
67 things taken 21 at a time is 129728497393775280 exactly.
34 things taken 34 at a time is 1 exactly.
12 things taken 11 at a time is 12 exactly.
90 things taken 6 at a time is 622614630 exactly.
80 things taken 7 at a time is 3176716400 exactly.
70 things taken 7 at a time is 1198774720 exactly.
60 things taken 8 at a time is 2558620845 exactly.
50 things taken 9 at a time is 2505433700 exactly.
45 things taken 10 at a time is 3190187286 exactly.
INPUT
100 20
100 90
100 85
88 12
67 12
100 6
23 5
34 20
17 9
98 6
67 21
34 34
12 11
90 6
80 7
70 7
60 8
50 9
45 10
OUTPUT
100 things taken 20 at a time is 535983370403809682000 exactly.
100 things taken 90 at a time is 17310309456440 exactly.
100 things taken 85 at a time is 253338471349988640 exactly.
88 things taken 12 at a time is 205371886988268 exactly.
67 things taken 12 at a time is 5996962277488 exactly.
100 things taken 6 at a time is 1192052400 exactly.
23 things taken 5 at a time is 33649 exactly.
34 things taken 20 at a time is 1391975640 exactly.
17 things taken 9 at a time is 24310 exactly.
98 things taken 6 at a time is 1052618392 exactly.
67 things taken 21 at a time is 129728497393775280 exactly.
34 things taken 34 at a time is 1 exactly.
12 things taken 11 at a time is 12 exactly.
90 things taken 6 at a time is 622614630 exactly.
80 things taken 7 at a time is 3176716400 exactly.
70 things taken 7 at a time is 1198774720 exactly.
60 things taken 8 at a time is 2558620845 exactly.
50 things taken 9 at a time is 2505433700 exactly.
45 things taken 10 at a time is 3190187286 exactly.
this is my code,maybe someone can help me,i got a WA
[cpp]
#include <iostream.h>
int main(int argc, char* argv[])
{
int n,m,loops,loopm,p,i,loop,temp;
long long mo[2],so[2];
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
long long mother[100],son[100],answer,sums,summ;
while(cin>>n>>m)
{
if(n==m && m==0) break;
so[0]=nm+1;
so[1]=n;
mo[0]=1;
mo[1]=m;
if(m>nm+1)
{
mo[1]=nm;
so[0]=m+1;
}
/*son=1;
for(;so[0]<=so[1];so[0]++)
son*=so[0];
cout<<son<<endl;
mother=1;
for(;mo[0]<=mo[1];mo[0]++)
mother*=mo[0];
cout<<mother<<endl;
answer=son/mother;*/
loops=1;
son[0]=so[0];
while(loops<=so[1]so[0])
{
son[loops]=son[loops1]+1;
loops++;
}
loops;
loopm=1;
mother[0]=mo[0];
while(loopm<=mo[1]mo[0])
{
mother[loopm]=mother[loopm1]+1;
loopm++;
}
loopm;
for(p=0;p<25;p++)
{
loop=loops;
while(loop>=0)
{
if (son[loop]%prime[p]==0)
{
for(i=0;i<=loopm;i++)
if(mother%prime[p]==0)
{
son[loop]/=prime[p];
mother/=prime[p];
if(son[loop]%prime[p]==0) continue;
else break;
}
}
loop;
}
}
/*temp=loops;
while(temp>=0)
{
cout<<son[temp]<<endl;
temp;
}
temp=loopm;
while(temp>=0)
{
cout<<mother[temp]<<endl;
temp;
}
*/
sums=1;
while(loops>=0)
{
sums*=son[loops];
loops;
}
summ=1;
while(loopm>=0)
{
summ*=mother[loopm];
loopm;
}
answer=sums/summ;
cout<<n<<" things taken "<<m<<" at a time is "<<answer<<" exactly."<<endl;
}
return 0;
}[/cpp]
[cpp]
#include <iostream.h>
int main(int argc, char* argv[])
{
int n,m,loops,loopm,p,i,loop,temp;
long long mo[2],so[2];
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
long long mother[100],son[100],answer,sums,summ;
while(cin>>n>>m)
{
if(n==m && m==0) break;
so[0]=nm+1;
so[1]=n;
mo[0]=1;
mo[1]=m;
if(m>nm+1)
{
mo[1]=nm;
so[0]=m+1;
}
/*son=1;
for(;so[0]<=so[1];so[0]++)
son*=so[0];
cout<<son<<endl;
mother=1;
for(;mo[0]<=mo[1];mo[0]++)
mother*=mo[0];
cout<<mother<<endl;
answer=son/mother;*/
loops=1;
son[0]=so[0];
while(loops<=so[1]so[0])
{
son[loops]=son[loops1]+1;
loops++;
}
loops;
loopm=1;
mother[0]=mo[0];
while(loopm<=mo[1]mo[0])
{
mother[loopm]=mother[loopm1]+1;
loopm++;
}
loopm;
for(p=0;p<25;p++)
{
loop=loops;
while(loop>=0)
{
if (son[loop]%prime[p]==0)
{
for(i=0;i<=loopm;i++)
if(mother%prime[p]==0)
{
son[loop]/=prime[p];
mother/=prime[p];
if(son[loop]%prime[p]==0) continue;
else break;
}
}
loop;
}
}
/*temp=loops;
while(temp>=0)
{
cout<<son[temp]<<endl;
temp;
}
temp=loopm;
while(temp>=0)
{
cout<<mother[temp]<<endl;
temp;
}
*/
sums=1;
while(loops>=0)
{
sums*=son[loops];
loops;
}
summ=1;
while(loopm>=0)
{
summ*=mother[loopm];
loopm;
}
answer=sums/summ;
cout<<n<<" things taken "<<m<<" at a time is "<<answer<<" exactly."<<endl;
}
return 0;
}[/cpp]
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
"Hold what you really know and tell what you do not know this will lead to knowledge."Confucius
tip for 369
After viewing the other posts about this problem, I'm surprised no one posted anything about the simplest way to solve it: Pascal's Triangle... very easy!
For those who don't know, let C(n,k) denote n things taken k at a time. The base cases are C(n,0) = 1 and C(n,n) 1. The others are C(n,k) = C(n1, k) + C(n1, k1). This is similar to a dynamic programming solution.
Now, the problem also says
Hope this helps!
For those who don't know, let C(n,k) denote n things taken k at a time. The base cases are C(n,0) = 1 and C(n,n) 1. The others are C(n,k) = C(n1, k) + C(n1, k1). This is similar to a dynamic programming solution.
Now, the problem also says
however some combinations, like C(100, 50) don't fit even in long long, so I used BigNum in my ACC solution. But this might not be necessary, because the judge may not be testing those cases... anyone knows anything about this?You may assume that the final value of C will fit in a 32bit Pascal LongInt or a C long.
Hope this helps!
 Ghust_omega
 Experienced poster
 Posts: 115
 Joined: Tue Apr 06, 2004 7:04 pm
 Location: Venezuela

 New poster
 Posts: 12
 Joined: Mon Mar 28, 2005 7:55 pm
 Contact:

 New poster
 Posts: 12
 Joined: Mon Mar 28, 2005 7:55 pm
 Contact:

 New poster
 Posts: 12
 Joined: Mon Mar 28, 2005 7:55 pm
 Contact:
My AC solution is as follows:
c = 1;
for (i=N,j=1;j<=R;i,j++)
c=(c*i)/j;
Here, R is the minimum of M or NM.
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).]
c = 1;
for (i=N,j=1;j<=R;i,j++)
c=(c*i)/j;
Here, R is the minimum of M or NM.
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).]