557 - Burger

[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]

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

[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]

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]

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]

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.

[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]

[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]

does anyone can explain how this algorithm work

i am confused at this problem

[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]

My AC solution produce the same ans

[howardcheng]

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

Code: Select all

code removed

[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?