[HOJ 277][GCJ 2013 1B]Falling Diamonds

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

我們先把鑽石的位置依照對原點的距離(|X|+|Y|)分成好多層，像屋頂一樣，定原點那顆鑽石的位置為第1層
可以觀察到，鑽石要跑到第n層之前，必須先把第n-1層填滿(除非n=1)
因此，我們可以先讓鑽石下落，直到剩餘的鑽石無法再填滿新的一層為止，這時鑽石會堆成一個完美的45度等腰三角形(以下叫做金字塔)，機率為1
如果(X,Y)在金字塔裡面，那麼答案是1.0
如果新的一層填滿了，還是碰不到(X,Y)，那麼答案是0.0
再來可以發現，X的正負號不影響答案，如果X=0，那麼答案為0.0(想一想，為甚麼XD)
所以我們只考慮X>0，也就是右側的情況
我們可以先算出沒有鑽石的機率，再用1.0去扣掉
設右側至少要堆k顆鑽石才能到達(X,Y)，剩下r顆鑽石可以堆
考慮每一顆鑽石掉下來會有各一半的機率往左或往右走，因此我們得到沒有鑽石的機率是
Sum{C(r,i)/(2^r),i=0~k-1}
注意，堆在左側的鑽石數量為r-i，而這個數字有可能大於金字塔的高度！
這時，有幾顆鑽石會因為疊太高而滑到右邊來，只要確認一下這種情況右側的鑽石有沒有達到k顆即可
算完以上機率後，用1.0減掉就是答案了
或者像我一樣直接從1.0慢慢扣也是可以

然後別像我一樣也把double寫成int然後一直回傳0和1 XD

code:

#include<cstdio>
#include<cmath>
#include<cassert>
#include<vector>
using namespace std;
int N,X,Y;
const double LogTwo=log(2.0);
vector<double>LEVEL;
double Level(const int i)
{
    if(i<(int)LEVEL.size())return LEVEL[i];
    LEVEL.push_back(Level(i-1)+log(i));
//    printf("level %d=%.9f\n",i,exp(LEVEL[i]));
    return LEVEL[i];
}
double F(const int a,const int b)
{
    const double ans=exp(Level(a)-Level(b)-Level(a-b)-a*LogTwo);
//    printf("F(%d,%d)=%.9f\n",a,b,ans);
    return ans;
}
double Solve()
{
    //1,6,15,28
    int v=sqrt(N*2);
    if(v*(v+1)/2>N)v--;
    assert(v*(v+1)/2<=N&&(v+1)*(v+2)/2>N);
    if(v%2==0)v--;
    const int remain=N-v*(v+1)/2;
//    printf("v=%d\n",v);
    if(v-1>=X+Y)return 1.0;
    else if(v+1<X+Y)return 0.0;
//    puts("pass");
    if(Y==v+1)return 0.0;
    double ans=1.0;
    for(int i=0;i<=Y&&i<=remain;i++)if(remain-i<=v+1||i+(remain-i)-(v+1)<=Y)ans-=F(remain,i);
    return ans;
}
int main()
{
    LEVEL.push_back(0.0);
    int testcase;scanf("%d",&testcase);
    while(testcase--)
    {
        scanf("%d%d%d",&N,&X,&Y);
        if(X<0)X=-X;
        if((X+Y)%2==1)
        {
            if(Y==0)X--;
            else Y--;
        }
        printf("%.9f\n",Solve());
    }
    return 0;
}
/*
5 1 2
*/