[Login|Register]
Problems

Status

Rank

Problem 1388
钻石
Time Limit: 3000ms
Memory Limit: 65536kb
Description
天上掉钻石了!阿泰正在买钻石可能着陆的土地。他需要你帮忙算一下

钻石的形状是一个正方形,顶点的坐标分别是(X-1,Y), (X, Y+1), (X+1,Y),(X,Y-1)。(X, Y)是钻石的中心点。所有的钻石都是在x-y二维平面上,x是横轴,y是纵轴。地面是Y=0,Y>0表示地表之上。


钻石每单位时间沿着Y轴下降1,也就是说它们从(0,Y)开始下降,Y是一个很大的数,在降落到地面之前或碰到其他钻石之前一直垂直降落。

当一个钻石掉到地面的时候,它就开始滚到它的一角插到地面里。也就是说所有的钻石都会在中心位于Y=0的时候停止滚动。

当一个钻石打到另一个钻石了(顶点对顶点),它等概率的向左下或者向右下方向下滑(不滚)。如果有一个方向已经有钻石了,它就不向那个方向滑了。如果两个方向都已经有钻石了,它就插在那两个钻石之间。

考虑上图:第一个钻石会直接打到地上并且一半儿插进地里,它的中心最终会位于(0,0)。第二个钻石可能滑向左下方或者右下方,在我们的图上,它滑向左下方了,最终插到地里,中心停在(-2, 0)。第三个钻石一开始也会打到第一个钻石上,也有可能向左下或者右下滑,在图上,它往左下方滑了并且卡在第一个和第二个钻石的缝里,中心停在(-1, 1)。第四个钻石当打到第一个钻石的时候没有别的选择了(因为左边已经被第三个钻石挡住了),所以它只能往右滑,插在地里了,中心停在(2,0)。
Input
第一行是一个整数T,表示输入数据的组数。下面跟着T行。
每行数据包含3个整数:N:下落钻石的个数,X,Y表示阿泰感兴趣的地点。(X,Y)不一定位于地面。
1 <= T <= 100
-10000 <= X <= 10000
0 <= Y <= 10000
1 <= N <= 20
X + Y是偶数
Output
每一组测试数据输出一行“Case #x: p"。x表示这是第几组测试数据,p表示N个钻石中的一个的中心恰好位于(X,Y)的概率。请用printf("%.6lf", answer);来输出你的答案,即截取小数点后的六位输出。
Sample Input
7
1 0 0
1 0 2
3 0 0
3 2 0
3 1 1
4 1 1
4 0 2
Sample Output
Case #1: 1.000000
Case #2: 0.000000
Case #3: 1.000000
Case #4: 0.750000
Case #5: 0.250000
Case #6: 0.500000
Case #7: 0.000000
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).