530 - Binomial Showdown

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Sun Oct 17, 2004 2:32 pm

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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Mon Oct 18, 2004 12:09 pm


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

Re: WA in 0.000 s

Post by Hedge » Wed Nov 24, 2004 12:39 pm

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

Post by WR » Wed Nov 24, 2004 1:50 pm

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.

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

530 Binomial Showdown

Post by leonardooo » Mon Nov 29, 2004 11:10 am

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]

:cry:

thx
Eu sou foda? N

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

Post by Ming Han » Tue Nov 30, 2004 7:30 pm

:: HanWorks ::

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by Rocky » Wed Dec 01, 2004 12:31 pm

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

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

Post by Ming Han » Wed Dec 01, 2004 5:57 pm

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

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

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

Post by leonardooo » Wed Dec 01, 2004 8:44 pm

thanks Guys, now I got AC !!! :lol:

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]

:lol: :) :D :P :wink:
Eu sou foda? N

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

530

Post by murkho » Tue Apr 12, 2005 8:32 pm

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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Apr 12, 2005 10:22 pm

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

Post by DerekG » Mon Apr 18, 2005 12:28 am

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
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Mon Apr 18, 2005 12:49 am

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

Post by DerekG » Mon Apr 18, 2005 3:03 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
Location: bangladesh
Contact:

530:confused WA?

Post by 59557RC » Tue Sep 06, 2005 10:40 pm

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

Post Reply

Return to “Volume 5 (500-599)”