557 - Burger

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
eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

557 - Burger

Post by eloha »

I know the math formula for this problem.
But the number of people is so big that I can not handle.
Can anyone tell me how to deal with that?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

if that's the case, you have to implement a big int class...

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Use Log

Post by shahriar_manzoor »

U can use log because only the intermediate results are big, not the final one. For example

log_ans=log(p!/(q!/r!)*2^(-n))
=log(p!)-log(q!)-log(r!)-n*log(2);

ans=pow(base,log_ans);

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha »

I got TLE after I use log(). I don't know what heppen! Please help me!
The following is my core code:
[c]
double count(int m)
{
int i,j=m/2;
double log_ans,ans;

for(log_ans=0.0, i=0; i<j; i++)
log_ans += log(m-i) - log(j-i) ;

log_ans -= log(2.0)*(double)m;
ans = exp(log_ans);
return ans;
}
[/c]

Pasq
New poster
Posts: 5
Joined: Mon Jun 24, 2002 5:53 pm

Post by Pasq »

Don't do it in this way. Use an array[1..100000] where you remember every log(n!). Then your formula is very simple.

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha »

Thank pasq for your hint.
I finally find the fomula between C(2(k+1),(k+1)) and C(2k,k)
So I can pre caculate the table.
Got AC now. :D

Shantanu
New poster
Posts: 8
Joined: Sun Oct 20, 2002 6:44 am

Post by Shantanu »

I use the pre calculate proecess and find the res using this.
But i got TLE. Help me

Code: Select all

long double do_it(long n)
{
	n-=2;
                long double rs=1,r1;
	long p=n/2;

	for(;p>0;)
	{
		r1=p*4;
		r1=n/r1;
		rs*=r1;
		n--;p--;
	}
	rs=1-rs;
	return rs;
}

tonyk
New poster
Posts: 7
Joined: Mon May 05, 2003 5:11 pm

What's wrong with my program?? Help!!

Post by tonyk »

[cpp]#include <iostream>
using namespace std;
int main() {
long double proba[50001];
int i,n,num;
proba[0]=1;
proba[1]=0.5;
for(i=2;i<=500;i++)
proba=proba[i-1]*(long double)(2*i-1)/(long double)(2*i);
cin>>n;
for(i=0;i<n;i++)
{
cin>>num;
{
cout.setf(ios::fixed);
cout.precision(4);
cout << 1-proba[num/2-1] << endl;
}
}
return 0;
}[/cpp]

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Post by DD »

does anyone can explain how this algorithm work

i am confused at this problem :cry:

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Can someone please check this I/O?

I just don't want to give up on Java, but I will probably have to...
21
2
4
6
8
10
20
50
100
200
256
500
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
0.0000
0.5000
0.6250
0.6875
0.7266
0.8145
0.8854
0.9196
0.9434
0.9500
0.9643
0.9747
0.9822
0.9854
0.9874
0.9887
0.9897
0.9905
0.9911
0.9916
0.9920
Thanks,
Darko

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv »

My AC solution produce the same ans

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Re: 557 Burger

Post by howardcheng »

What's wrong with this simple code? I get WA even after changing precision.

Code: Select all

code removed

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Re: 557 Burger

Post by howardcheng »

I finally got AC, simply by using C++ output instead of C output. I used

cout << fixed << setprecision(4) << ...

instead of

printf("%.4f\n", ...)

and it is accepted. Both versions give the same results on all possible inputs on my machine. Is there anything funny about the rounding mode?

Post Reply

Return to “Volume 5 (500-599)”