530 - Binomial Showdown

[Raiyan Kamal]

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]

This post will help you:
http://online-judge.uva.es/board/viewto ... hlight=530

[Hedge]

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]

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]

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) {

String input = readLn();
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");
input = readLn();
continue;
}

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

if(k == 1) {
System.out.println(n);
input = readLn();
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);
input = readLn();
}

}

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

static String readLn() {
String newLine = System.getProperty("line.separator");
StringBuffer buffer = new StringBuffer();
int car = -1;
try {
car = System.in.read();
while ((car > 0) && (car != newLine.charAt(0))) {
buffer.append((char)car);
car = System.in.read();
}
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

[Ming Han]

I suggest:
http://online-judge.uva.es/board/viewto ... hlight=530
http://online-judge.uva.es/board/viewto ... hlight=530

[Rocky]

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]

http://mathworld.wolfram.com/PascalsTriangle.html

Quite a good site to understand more....

[leonardooo]

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]

[murkho]

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[150],k_a[150];
//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]

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]

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);
}

[Mohammad Mahmudur Rahman]

Try using long double...

[DerekG]

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]

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;


}