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

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Mon Nov 10, 2003 5:01 am

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. :wink: :wink: :wink:
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.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Nov 10, 2003 10:01 am

You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long.
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.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

Post by osan » Mon Nov 10, 2003 4:21 pm

dear Joseph Kurniawan

thanks for your messege. actually i was confused about that. well i will check it in GCC.

i'm new in porgramming side. so don't have that kind of knowledge.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

Post by osan » Mon Nov 10, 2003 4:39 pm

junjieliang
i used long double to hold the final value
this time WA
what next...............?

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

INPUT OUTPUT FOR 369

Post by osan » Sat Dec 27, 2003 8:29 pm

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.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

INPUT OUTPUT FOR 369

Post by osan » Sat Dec 27, 2003 8:30 pm

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.

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

INPUT OUTPUT FOR 369

Post by osan » Sat Dec 27, 2003 8:31 pm

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.

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Mon Jan 26, 2004 11:00 am

hey,i just wondering.what the type are u using?i can't reach such a long number even used the long long :roll:
"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

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Mon Jan 26, 2004 11:02 am

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]=n-m+1;
so[1]=n;
mo[0]=1;
mo[1]=m;
if(m>n-m+1)
{
mo[1]=n-m;
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[loops-1]+1;
loops++;
}
loops--;
loopm=1;
mother[0]=mo[0];
while(loopm<=mo[1]-mo[0])
{
mother[loopm]=mother[loopm-1]+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

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

tip for 369

Post by gits » Thu Dec 30, 2004 4:53 pm

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(n-1, k) + C(n-1, k-1). This is similar to a dynamic programming solution.

Now, the problem also says
You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long.
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?

Hope this helps! :)

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Dec 31, 2004 1:52 am

Hi !! gits your formula is the way the I solved this one and, I used long double for solved.....
Hope it Helps
Keep posting !!

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

Post by Lord Nemrod » Wed Apr 06, 2005 1:27 pm

I haven't read your code, but there is a formula that can help. Precalculate everything first using the formula
C(N, M) = C(N-1, M-1)+C(N-1, M). Use DP. Hope this helps

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

Post by Lord Nemrod » Wed Apr 06, 2005 1:28 pm

I haven't read your code, but there is a formula that can help. Precalculate everything first using the formula
C(N, M) = C(N-1, M-1)+C(N-1, M). Use DP. Hope this helps

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

Post by Lord Nemrod » Wed Apr 06, 2005 1:34 pm

Guys,
Try to use the following formula and unsignel long will be enough.
C(N, M) = C(N-1, M-1)+C(N-1, M). Take a matrix and systematiccaly calculate all values of C for all M and N. Then for every input output MATRIX(N, M). No need to use Factorial at all. Hope this helps

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

Post by IIUC GOLD » Thu Apr 07, 2005 8:35 am

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 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).]

Post Reply

Return to “Volume 3 (300-399)”