| [Home|Training|Problems|Contests|C Language] | [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 |