Page 1 of 1
557 - Burger
Posted: Sat Mar 01, 2003 11:04 am
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?
Posted: Sun Mar 02, 2003 1:21 am
by Larry
if that's the case, you have to implement a big int class...
Use Log
Posted: Sun Mar 02, 2003 2:23 am
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);
Posted: Mon Mar 03, 2003 9:38 am
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]
Posted: Tue Mar 18, 2003 11:38 pm
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.
Posted: Wed Mar 19, 2003 8:13 am
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.
Posted: Sat May 03, 2003 10:12 am
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;
}
What's wrong with my program?? Help!!
Posted: Wed May 07, 2003 8:28 am
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]
Posted: Fri Sep 12, 2003 5:15 am
by DD
does anyone can explain how this algorithm work
i am confused at this problem
Posted: Fri Nov 25, 2005 7:29 am
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
Posted: Mon Nov 28, 2005 7:57 am
by roticv
My AC solution produce the same ans
Re: 557 Burger
Posted: Thu Jul 24, 2008 4:16 am
by howardcheng
What's wrong with this simple code? I get WA even after changing precision.
Re: 557 Burger
Posted: Tue Nov 17, 2009 6:57 am
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?