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
edmanm
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

530 - Binomial Showdown

Post by edmanm » Sat Feb 09, 2002 8:17 am

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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Sat Feb 09, 2002 10:53 am

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 :smile:

edmanm
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

Post by edmanm » Sat Feb 09, 2002 11:20 am

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
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

Post by edmanm » Sat Feb 09, 2002 11:22 am

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Feb 09, 2002 10:21 pm

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
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

Post by edmanm » Sun Feb 10, 2002 12:02 am

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
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

Post by edmanm » Sun Feb 10, 2002 1:57 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 10, 2002 3:42 am

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

edmanm
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

Post by edmanm » Sun Feb 10, 2002 3:53 am

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
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

Post by edmanm » Sun Feb 10, 2002 8:20 am

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Fri Mar 22, 2002 7:58 am

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

why I get signal 11 (SIGSEGV) again!!?

Post by hank » Tue Jul 02, 2002 5:07 am

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Tue Jul 02, 2002 5:10 am

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Tue Jul 02, 2002 5:13 am

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Tue Jul 02, 2002 5:20 am

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

Thx!!

Post Reply

Return to “Volume 5 (500-599)”