Chieh's Blog

Because Of Coding

ZOJ Problem Set - 2949 Coins of Luck

Chieh posted @ 2015年8月21日 14:32 in NO Answer No Speak , 275 阅读
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define INF 1e-9
using namespace std;
const int maxn=1234;
int n;
double ai[maxn][maxn];
double bi[maxn][maxn*2];
double ans[maxn];
void init()
{
    memset(ai,0,sizeof(ai));
    memset(bi,0,sizeof(bi));
    ai[0][0]=1;
    for(int i=1; i<=2*1000; i++)
    {
        //w
        for(int j=1; j<=i; j++)
        {
            int w=j;
            int b=i-j;
            if(w<=1000&&b<1000)
            {
                ai[w][b]+=(ai[w-1][b]/2.0);
                if(w>b)
                bi[w][w+b]+=(ai[w-1][b]/2.0);
            }
        }
        //b
        for(int j=1; j<=i; j++)
        {
            int w=i-j;
            int b=j;
            if(b<=1000&&w<1000)
            {
                ai[w][b]+=(ai[w][b-1]/2.0);
                if(b>w)
                bi[b][w+b]+=(ai[w][b-1]/2.0);
            }
        }
    }

    for(int i=1; i<=1000; i++)
    {
        double tm=0;
        for(int j=0; j<=i*2; j++)
        {
            tm+=bi[i][j]*j;
        }
        ans[i]=tm;
    }

}

void play()
{
    scanf("%d",&n);
    printf("%.2f\n",ans[n]);


}
int T;
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {

        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define INF 1e-9
using namespace std;
const int maxn=1234;
int n;
double ai[maxn][maxn];
double ans[maxn];
void init()
{
    memset(ai,0,sizeof(ai));
    for(int i=0; i<=1000; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            int w=i;
            int b=j;
            if(w==0&&b==0)ai[i][j]=1;
            else
            {
                if(w!=0)
                {
                    ai[w][b]+=(ai[w-1][b]/2.0);
                }
                if(b!=0)
                {
                    ai[w][b]+=(ai[w][b-1]/2.0);
                }
                if(w>b)
                {
                    ans[w]+=(ai[w-1][b]/2.0)*(w+b);
                }
                if(b>w)
                {
                    ans[b]+=(ai[w][b-1]/2.0)*(w+b);
                }
            }
        }
    }
}

void play()
{
    scanf("%d",&n);
    printf("%.2f\n",ans[n]);


}
int T;
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {

        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter