## 530 - Binomial Showdown

Moderator: Board moderators

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
Perhaps you are consuming too much time by multiplying numbers one after another and in determining the GCD. Think how can you do it by using addition instead of multiplication

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 pm

### Re: WA in 0.000 s

Hi, I think i know what might be the problem of your program. You declare 'p' as an unsigned long integer, but you print it with "%ld". This converts it to an singed long int, so it might end up as a negative value if it is above 2^31. You should print unsigned long int with "%lu", to be sure that values above 2^31 are positive.
edit: Sorry, i just read the specification. The result will always be below 2^31. So what I mentioned wont affect you for this problem. But nevertheless you should always print unsinged integers with %u not %d.
Actually i used unsigned long long integer for the intermediate results. Maybe you should take a close look at the binom function, and if the values there might overflow.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks for the post.

I've solved this problem shortly after the previous post (using double, by the way). Of course my program caused the WA, but at that time I just wasn't sure if the OJ returns a WA immediately after a wrong answer or if it first reads all records and complains afterwards.

leonardooo
New poster
Posts: 8
Joined: Sun Nov 28, 2004 9:26 am
Location: Campina Grande - PB / Brazil

### 530 Binomial Showdown

I dont know why my code is wrong, anybody has special test cases ?

[java]
//Problem 530

import java.util.*;
class Main {

public static void main(String[] args) {

while(input != null && !input.equals("0 0")) {

StringTokenizer st = new StringTokenizer(input);
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());

if(k > n) {
System.out.println("0");
continue;
}

if(k == n) {
System.out.println("1");
continue;
}

if(k == 1) {
System.out.println(n);
continue;
}

long result;
long divfat;

if(n-k > k) {
divfat = fat(n-k+1,n);
result = divfat / fat(1,k);
} else {
divfat = fat(k+1,n);
result = divfat / fat(1,n-k);
}

System.out.println(result);
}

}

static long fat(int ini, int fim) {
long result = 1;
for(int i = ini; i <= fim; i++) result *= i;
return result;
}

String newLine = System.getProperty("line.separator");
StringBuffer buffer = new StringBuffer();
int car = -1;
try {
while ((car > 0) && (car != newLine.charAt(0))) {
buffer.append((char)car);
}
if (car == newLine.charAt(0))
System.in.skip(newLine.length() - 1);
} catch (java.io.IOException e) { return (null);}
if ((car < 0) && (buffer.length() == 0)) return (null);
return (buffer.toString()).trim();
}

}
[/java] thx
Eu sou foda? N

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:
:: HanWorks ::

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:
I am not expert in java so i can't understand you'r code
BUT I suggest that BY simplification the main equation become very
simple and check that Whether the mod of two number is ZERO
if ZERO then dived them and multiply the result of divide with result1 OTHERWISE multiply them directly with result1 and result2 AND printf the result of result1/result2
.....

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:
http://mathworld.wolfram.com/PascalsTriangle.html

Quite a good site to understand more....
:: HanWorks ::

leonardooo
New poster
Posts: 8
Joined: Sun Nov 28, 2004 9:26 am
Location: Campina Grande - PB / Brazil
thanks Guys, now I got AC !!! I stored all numbers in a int array: 10! = [1,2,3,4,5,6,7,8,9,10] 5! = [1,2,3,4,5]

I used this algorithm: 10! / 5!

[java]
for(i = 0; i < 10; i++)
for(j = 0; j < 5; j++)
if( array1 % array2[j] == 0)
array1 /= array2[j];
array2[j] = 1;
[/java]     Eu sou foda? N

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

### 530

can anybody tell me the reason to get wa?????

Code: Select all

``````
#include<stdio.h>
//#include<math.h>
int main()
{
long int  n,ans;long int index,i,j,k;
long int n_a,k_a;
//freopen("F:\\530.txt","r",stdin);
while(scanf("%ld %ld",&n,&k)==2 )
{
if (n == 0 && k == 0)
break;
if(k>n/2)
k = (long)n -k;
index = -1;
ans = 1;
for(i = (long) n;i > n-k;i--)
n_a[++index] =i;

index = -1;
for(i = k;i>1;i--)
k_a[++index] = i;

for(i = 0;i<k;i++)
for(j=0;j<k-1;j++)
{
if(k_a[j]!=1 && (n_a[i]%k_a[j]==0))
{
n_a[i] =  n_a[i] /k_a[j];
k_a[j] = 1;

}

}
for(i = 0;i<k;i++)
ans = ans*n_a[i];

printf("%.0ld\n",ans);

}

return 0;
}
``````

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
You have an overflow in your intermediate calculations, as n_a can be over 2^31. Remember that both long int and int is 32 bits wide. If you need a 64-bit datatype, use long long.

DerekG
New poster
Posts: 2
Joined: Mon Apr 18, 2005 12:26 am

### 530 WA

can anyone please help me on this my code works fine on my machine .. maybe im misunderstanding something but any help is appreciated Thx.

#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;
int factorial(int n);
int gcd(int a, int b);
int main(int argc, char *argv[])
{
while(1){
long long n, d, sum=1, nminusd=0, temp=0;
cin>>n>>d;
if(n==0) return 0;
if(n==d || d==0){
cout<<"1"<<endl;
return 0;
}
if(d>n){
cout<<"0"<<endl;
return 0;
}
if(d>=(n-d)){
nminusd=factorial(n-d);
for(int i=n; i>d; i--){
sum*=i;
temp=sum;
sum/=gcd(sum, nminusd);
nminusd/=gcd(temp, nminusd);
}
cout<<sum<<endl;
}
else{
nminusd=factorial(d);
for(int i=n; i>(n-d); i--){
sum*=i;
temp=sum;
sum/=gcd(sum, nminusd);
nminusd/=gcd(temp, nminusd);
}
cout<<sum<<endl;
}
}
return 0;
}
int factorial(int n)
{
int sum=1;
for(int i=n; i>1; i--)
sum*=i;
return sum;
}

int gcd(int a, int b)
{
long r;
if(a < 0) a = -a;
if(b < 0) b = -b;

if(a == 0) return(b);
if(b == 0) return(a);

while(b > 0)
{
r = a % b;
a = b;
b = r;
}
return(a);
}

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
Try using long double...
You should never take more than you give in the circle of life.

DerekG
New poster
Posts: 2
Joined: Mon Apr 18, 2005 12:26 am
i tried that, changing as much to long double as i could wihle still having it work and that still failed... any other ideas? my code works perfectly on my stuff, does my readin look ok for how they run their test cases? any idea how large there test cases go i thought this was supposed to fit into a regular int? if so, all this long and double stuff shouldnt be needed by reducing the sum by the gcd each iteration...

59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Contact:

### 530:confused WA?

i used long double n dividebygcd but why WA:

#include<stdio.h>
#include<math.h>

long double gcd(long double a,long double b)
{
if(fmod(a,b)==0) return b; else return gcd(b,fmod(a,b));
}

int main()
{

long double g,i,j,k,n,mul,div;
double up,down;
scanf("%Lf %Lf",&n,&k);
while(n!=0 && k!=0){
up=1;down=1;
if(k>n/2) k=n-k;
for(i=k;i>0;i--){
j=n-i+1;
mul=j;div=i;
g=gcd(mul,div);mul/=g;div/=g;
g=gcd(mul,down);mul/=g;down/=g;
g=gcd(up,div);div/=g;up/=g;

up*=mul;down*=div;
}
printf("%.0Lf\n",up/down);
scanf("%Lf %Lf",&n,&k);
}
return 0;

}
aaa