530  Binomial Showdown
Moderator: Board moderators
Thanks Claudio,
Of course you're first remark is correct! Silly mistake.
As to the 2nd remark, I thought "... just in case!, maybe the
input isn't n, k but k, n". But as you said, that wouldn't cause
this error.
As a third measure I corrected the newline.
And no, I don't have the judge's input data, but a fast
GCD algorithm from Steven Halim's site.
The trouble is, that other programs show the same behaviour. And they
should run at least one or two tenth of a second.
Ok, I just submitted the new version and still have a WA but this time
the program ran 0.002 seconds. So the program's not correct but at least
the main function seems to work. I guess it was the "n 0" input that
caused that response.
Thanks again
Of course you're first remark is correct! Silly mistake.
As to the 2nd remark, I thought "... just in case!, maybe the
input isn't n, k but k, n". But as you said, that wouldn't cause
this error.
As a third measure I corrected the newline.
And no, I don't have the judge's input data, but a fast
GCD algorithm from Steven Halim's site.
The trouble is, that other programs show the same behaviour. And they
should run at least one or two tenth of a second.
Ok, I just submitted the new version and still have a WA but this time
the program ran 0.002 seconds. So the program's not correct but at least
the main function seems to work. I guess it was the "n 0" input that
caused that response.
Thanks again
I just checked the stats for problem 530 and I see that there are far too many 0.000 accepted solutions, so probably the input data set is small.WR wrote:Ok, I just submitted the new version and still have a WA but this time
the program ran 0.002 seconds. So the program's not correct but at least
the main function seems to work. I guess it was the "n 0" input that
caused that response.
Maybe you should check the behaviour of your prog with input near or equal to MAXINT...
Ciao!!!
Claudio
530
Hi,
why does this program give a WA?
I wouldn't be too surprised if the message were TLE but it's WA.
The elements of the denominator array (karr) are 1 when leaving the function binom, so what remains to be done is the multiplication of
the elements of narr but that can't be helped.
The program certainly gives a wrong answer if the (intermediate)
results of that multiplication don't fit into an integer but as there is
nothing to divide by anymore I think I can ignore that for this problem.
The function GGT is from S. Halim's website and computes the greatest common denominator (GCD).
why does this program give a WA?
I wouldn't be too surprised if the message were TLE but it's WA.
The elements of the denominator array (karr) are 1 when leaving the function binom, so what remains to be done is the multiplication of
the elements of narr but that can't be helped.
The program certainly gives a wrong answer if the (intermediate)
results of that multiplication don't fit into an integer but as there is
nothing to divide by anymore I think I can ignore that for this problem.
The function GGT is from S. Halim's website and computes the greatest common denominator (GCD).
Code: Select all
#include <stdio.h> /* printf */
/*****************************
* ACM Contest  Problem 530 *
*****************************/
long GGT(long a1, long b1)
{
long a, b;
a = a1;
b = b1;
while (b > 0){
a %= b;
a += b;
b = ab;
a = b;
}
return a;
}
long Minimum(long a, long b)
{
if (a < b)
return a;
else
return b;
}
double binom(long m, long n)
{
long i, j, k, l, t;
static long narr[10000], karr[10000];
long na, ka;
short end;
double b;
if (m == n)
return 1;
else{
if (n < 2)
return m;
else{
k = Minimum(n,mn);
l = m  k;
for (i=0;i<k;i++){
karr[i] = i+1;
narr[i] = karr[i]+l;
}
for (i=k1;i>=0;i){
j = k1;
end = 0;
do{
do{
na = narr[i];
ka = karr[j];
if ((na < 2) && (ka < 2))
end = 1;
else{
t = GGT(na,ka);
if (t > 1){
narr[i] /= t;
karr[j] /= t;
}
}
}while ((t > 1) && (end != 1));
j;
}while ((j >= 0) && (end != 1));
}
b = 1;
for (i=0;i<k;i++)
b *= narr[i]/karr[i];
}
return b;
}
}
int main(void)
{
long k, n;
double p;
while (scanf("%ld %ld",&k,&n) == 2){
if ((k > 0)  (n > 0)){
p = k;
if (n == 0)
p = 1;
else
if (p > 1) p = binom(k,n);
printf("%.0lf\n",p);
}
}
return 0;
}

 New poster
 Posts: 19
 Joined: Thu May 02, 2002 5:47 am
 Location: Zhongshan (Sun Yatsen) University
Thozz: Recursive factorial, for shame.
This about this, your stack has enough room for maybe 50 depth, but what happens if you take Factorial(100)?
You end up with 100 factorials on the stack. Try using an iterative approach instead:
[cpp]long double Factorial(int n)
{
double value = 1;
for (int i = 2; i < n; i++)
value *= i;
return value;
}[/cpp]
Anyway, I think using double is sort of cheating, isn't it? Kind of defeats the purpose of this problem Well, if it gets AC, then it works okay I guess.
This about this, your stack has enough room for maybe 50 depth, but what happens if you take Factorial(100)?
You end up with 100 factorials on the stack. Try using an iterative approach instead:
[cpp]long double Factorial(int n)
{
double value = 1;
for (int i = 2; i < n; i++)
value *= i;
return value;
}[/cpp]
Anyway, I think using double is sort of cheating, isn't it? Kind of defeats the purpose of this problem Well, if it gets AC, then it works okay I guess.
530 Special cases.
I think I found a special case that is giving me WA, and I thought I'd share it.
Specifically, when k = 0, the output should = 1.
The way I had it set up, the program exited on k=0
Ohwell, its fixed now an I got AC.
Specifically, when k = 0, the output should = 1.
The way I had it set up, the program exited on k=0
Ohwell, its fixed now an I got AC.

 Experienced poster
 Posts: 122
 Joined: Tue Apr 16, 2002 10:07 am
Hello!
nCk = n! / k!(nk)!
for example,
7C4 = 7! / (4! * 3!)
= 7 * 6 * 5 * 4 * 3 * 2 * 1

(4 * 3 * 2 * 1) * (3 * 2 * 1)
= 7 * 6 * 5

3 * 2 * 1
= 7C3
100 C 99 = 100 C 1
1000 C 9998 = 1000 C 2
.
.
.
Try to do a loop for multiplying the numerator and the denominator;
whereby, we can reduce the numerator and the denominator to their lowest terms by dividing them with their greatest common divisor.
nCk = n! / k!(nk)!
for example,
7C4 = 7! / (4! * 3!)
= 7 * 6 * 5 * 4 * 3 * 2 * 1

(4 * 3 * 2 * 1) * (3 * 2 * 1)
= 7 * 6 * 5

3 * 2 * 1
= 7C3
100 C 99 = 100 C 1
1000 C 9998 = 1000 C 2
.
.
.
Try to do a loop for multiplying the numerator and the denominator;
whereby, we can reduce the numerator and the denominator to their lowest terms by dividing them with their greatest common divisor.
i try to use recursion to solve this problem..
but it was "runtime error?!"
could anyone please tell me why ?
here's my code ..
[c]#include <stdio.h>
int c(int n, int r) {
if (n==r) return 1;
if ((r==1)(!r)) return n;
return (c(n1,r1)+c(n1,r));
}
int main(void) {
int n, r;
while (scanf("%d %d", &n, &r)==2) {
if (!n&&!r) break;
printf("%d\n", c(n, r));
}
return 0;
}[/c]
but it was "runtime error?!"
could anyone please tell me why ?
here's my code ..
[c]#include <stdio.h>
int c(int n, int r) {
if (n==r) return 1;
if ((r==1)(!r)) return n;
return (c(n1,r1)+c(n1,r));
}
int main(void) {
int n, r;
while (scanf("%d %d", &n, &r)==2) {
if (!n&&!r) break;
printf("%d\n", c(n, r));
}
return 0;
}[/c]
Thanks for your help !
i try to use recursion to solve this problem..
but it was "runtime error?!"
could anyone please tell me why ?
here's my code ..
[c] Q_Q i was wrong.. [/c]
but it was "runtime error?!"
could anyone please tell me why ?
here's my code ..
[c] Q_Q i was wrong.. [/c]
Last edited by Frostina on Sun Jul 04, 2004 6:57 am, edited 1 time in total.
Thanks for your help !

 New poster
 Posts: 8
 Joined: Tue Oct 12, 2004 1:54 pm
 Location: IranTehran
 Contact:
530 Why TLE (Help Please)
This is my solution for 530. But I don't know why its TLE
Please help me !
Thanks
[cpp]
#include<stdio.h>
long long int gcd(long long int p,long long int q)
{
long long int temp;
while(q)
{
temp=p;
p=q;
q=temp%q;
}
return p;
}
int main()
{
long long int n,k;
long long int t,a,b;
while(scanf("%lld %lld",&n,&k),n!=0k!=0)
{
a=1;b=1;
for(int i=1;i<=k;i++)
{
a*=nk+i;
b*=i;
t=gcd(a,b);
a/=t;
b/=t;
}
printf("%lld\n",a);
}
return 0;
}
[/cpp]
Please help me !
Thanks
[cpp]
#include<stdio.h>
long long int gcd(long long int p,long long int q)
{
long long int temp;
while(q)
{
temp=p;
p=q;
q=temp%q;
}
return p;
}
int main()
{
long long int n,k;
long long int t,a,b;
while(scanf("%lld %lld",&n,&k),n!=0k!=0)
{
a=1;b=1;
for(int i=1;i<=k;i++)
{
a*=nk+i;
b*=i;
t=gcd(a,b);
a/=t;
b/=t;
}
printf("%lld\n",a);
}
return 0;
}
[/cpp]