Page 4 of 7

Posted: Mon Nov 10, 2003 5:01 am
by Joseph Kurniawan
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:

Posted: Mon Nov 10, 2003 10:01 am
by junjieliang
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.

Posted: Mon Nov 10, 2003 4:21 pm
by osan
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.

Posted: Mon Nov 10, 2003 4:39 pm
by osan
junjieliang
i used long double to hold the final value

INPUT OUTPUT FOR 369

Posted: Sat Dec 27, 2003 8:29 pm
by osan
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 OUTPUT FOR 369

Posted: Sat Dec 27, 2003 8:30 pm
by osan
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 OUTPUT FOR 369

Posted: Sat Dec 27, 2003 8:31 pm
by osan
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.

Posted: Mon Jan 26, 2004 11:00 am
by Morning
hey,i just wondering.what the type are u using?i can't reach such a long number even used the long long :roll:

Posted: Mon Jan 26, 2004 11:02 am
by Morning
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]

tip for 369

Posted: Thu Dec 30, 2004 4:53 pm
by gits
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! :)

Posted: Fri Dec 31, 2004 1:52 am
by Ghust_omega
Hi !! gits your formula is the way the I solved this one and, I used long double for solved.....
Hope it Helps
Keep posting !!

Posted: Wed Apr 06, 2005 1:27 pm
by Lord Nemrod
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

Posted: Wed Apr 06, 2005 1:28 pm
by Lord Nemrod
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

Posted: Wed Apr 06, 2005 1:34 pm
by Lord Nemrod
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

Posted: Thu Apr 07, 2005 8:35 am
by IIUC GOLD
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).]