Description

钻石正从天而降。人们开始购买钻石可能落下的位置，希望能拥有一颗真正落在那里的钻石。你现在被推荐了这样一个位置，想知道这是否值得购买。

钻石的形状，正如你所想，是菱形：对于某个中心 $(X, Y)$，它的四个顶点分别是 $(X-1, Y)$、$(X, Y+1)$、$(X+1, Y)$ 和 $(X, Y-1)$。所有的钻石都位于 $X$-$Y$ 平面上。$X$ 表示水平方向，$Y$ 表示竖直方向。地面在 $Y=0$，$Y$ 增大表示高于地面。

钻石依次沿着 $Y$ 轴落下。也就是说，它们从 $(0, Y)$（$Y$ 很大）的位置垂直下落，直到撞到地面或其他钻石为止。

当一颗钻石撞到地面时，它会继续下落，直到中心埋入地面，此时停止移动。也就是说，所有钻石只要中心到达 $Y=0$ 就会停止下落或滑动。

当一颗钻石顶点对顶点撞到另一颗钻石时，它可以开始沿着两个方向之一滑落：向左下或向右下，且不发生旋转。如果这两侧都没有被钻石挡住，则它以相等概率选择向左或向右滑落。如果某一侧被钻石挡住了，则它会一直沿着未被挡住的那一侧滑动，直到被其他钻石挡住或埋入地面。如果左右两侧都被挡住，则钻石就会停止。

请参考上图示例。第一颗钻石落地后，中心停在 $(0, 0)$。第二颗钻石有 $50\%$ 的概率向左或向右滑落。这里它向左滑落，最终停在 $(-2, 0)$。第三颗钻石也会撞到第一颗钻石，然后要么随机向右滑落并停在地面，要么向左滑落，最终停在已存在的两颗钻石之间的上方。这里它又向左滑落，最终停在 $(-1, 1)$。第四颗钻石没有选择，只能向右滑落并停在 $(2, 0)$。

Input Format

输入的第一行为测试用例数 $T$。接下来 $T$ 行，每行包含三个整数：落下的钻石数 $N$，以及你感兴趣的位置的坐标 $X, Y$。注意，你关注的位置不一定在地面或地面附近。

Output Format

对于每个测试用例，输出一行 "Case #x: p"，其中 $x$ 是测试用例编号（从 $1$ 开始），$p$ 是 $N$ 颗钻石中有一颗最终中心恰好落在 $(X, Y)$ 的概率。只要你的答案与正确答案的绝对误差不超过 $10^{-6}$，就会被判为正确。

7
1 0 0
1 0 2
3 0 0
3 2 0
3 1 1
4 1 1
4 0 2

Case #1: 1.0
Case #2: 0.0
Case #3: 1.0
Case #4: 0.75
Case #5: 0.25
Case #6: 0.5
Case #7: 0.0

Hint

限制条件

• $1 \leq T \leq 100$
• $-10,000 \leq X \leq 10,000$
• $0 \leq Y \leq 10,000$
• $X + Y$ 为偶数

小数据集（14 分，测试集 1 - 可见）

• $1 \leq N \leq 20$

大数据集（28 分，测试集 2 - 隐藏）

• $1 \leq N \leq 10^{6}$

翻译由 ChatGPT-4.1 完成。