530 - Binomial Showdown

[edmanm]

Can anybody offer any hints to solving problem #530 - Binomial Showdown? My first attempt at solving this problem resulted in an exceeded time limit. Any tips?

[cyfra]

Hi!

The answer in this this task is always less then 2^31.
It helps a lot.
But in the iinput can be the case :
2^31 1
and
2^31 2^31

Check your program for this data, I think that for one case it will be working very long.

I hope it will help you!

Good Luck

[edmanm]

Here is the code I submitted. It gives me the right answers to the sample input on my computer, but I get Time Limit Exceeded when I submit it for judging. Any input would be appreciated:


#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

main()
{
int num1, num2, i;
long double numerator, denominator, ans;
int n_minus_r;



#ifndef ONLINE_JUDGE
close (0); open ("input.in", O_RDONLY);
close (1); open ("output.out", O_WRONLY | O_CREAT, 0600);
#endif


while(scanf("%d %d", &num1, &num2) == 2)
{
numerator = 1;
denominator = 1;

n_minus_r = num1 - num2;

for(i=num1; i > n_minus_r; i--)
numerator = numerator * i;
for(i=num2; i > 1; i--)
denominator = denominator * i;

ans = numerator / denominator;

printf("%.fn", ans);

}

return 0;
}

[edmanm]

Perhaps using Pascal's Triangle would be a better way to approach this problem????

[Adrian Kuegel]

Add the following line to your code:
if (num1 - num2<num2) num2=num1-num2;

<font size=-1>[ This Message was edited by: Adrian Kuegel on 2002-02-09 21:40 ]</font>

[edmanm]

Thanks Adrian! Your line of code took care of my runtime error problem. But now I got a wrong answer. I think perhaps I'm using the wrong data type.

Any clues as to what the tricky input the judges uses?

[edmanm]

When testing my program using sample input, I get correct answers. Yet, when I submit my program, it says I have a wrong answer. What are the tricky inputs?

I've tried using sample inputs of num1 = 2^31 and num2 = 2^31, and num1 = 2^31 and num2 = 1, which seem to be about the two limits since the answer will fit into an integer. And my answers are correct on my machine! I've also experimented with num1 = 0 & num2 = 0. What gives?

[Adrian Kuegel]

I think you didnt consider this line in the description:
Input is terminated by two zeroes for n and k.

[edmanm]

You're right, I hadn't considered that! That'll teach me to read the problem more carefully. So, I fixed it to terminate when a 0 is read for num1 && num2. Unfortunately, I still get a Wrong Answer.

P.S. Thanks Adrian for helping me on this one.

[edmanm]

I got it! Yay! I just had to change my data type for storing the intermediate results from a long double to just a double. Thanks everybody for your help.

[Subeen]

using unsigned long I also got it A.C.
pascle's triangle also works ( but i didn't try it myself )

[hank]

I get
----------------------------
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 5.550 seconds.
-----------------------------
why?

my source is wrong?

(problem 530 in C)

#include "stdio.h"
int data[141],n,k;
long p;
void clear_data()
{
int i;
for(i=1;i<=140;i++)
data=0;
}
void run_data()
{
int i,r,q;
p=1;
i=n;
while(i>=2)
{
if(data==1&&data[i-1]==0)
{
data=0;
data[i-1]=1;
q=0;
for(r=i;r<=n;r++)
if(data[r]==1) q++;
for(r=i;r<=n;r++)
data[r]=0;
for(r=n;r>n-q;r--)
data[r]=1;
i=n;
p++;
}else{
i--;
}
}
}
void main()
{
int i;
while(1){
scanf("%d %d\n",&n,&k);
if(n==0&&k==0) break;
clear_data();
for(i=n;i>n-k;i--)
data=1;
run_data();
printf("%ld\n",p);
}

}

[10153EN]

First of all, why you post this message, which is about p530, in Volume I but not Volume V?

[hank]

i'm sorry!! ^_^|||

[hank]

anyone can help me?
Thanks very much..
my got signal 11 (SIGSEGV) many times...
I was confused..

Thx!!