## 557 - Burger

Moderator: Board moderators

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

### 557 - Burger

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:
if that's the case, you have to implement a big int class...
shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Use Log

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
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
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
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
New poster
Posts: 8
Joined: Sun Oct 20, 2002 6:44 am
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!!

[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:
does anyone can explain how this algorithm work

i am confused at this problem
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
My AC solution produce the same ans
howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

### Re: 557 Burger

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

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

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