← 返回题目列表

AtCoder · abc011_4

D. 大跳

中文机器翻译题面 查看原题

問題文

XY 起点和终点在坐标上。 每个都有 1 。 起点是 (0, 0) 目标点是 (X, Y) 。

你使用一种称为跳跃的移动方法来移动。 跳跃 如果您执行 1 次,您将得到以下结果 4 随机选择 1 进行了两次动作。

  • X 平行于轴 移动 +D 。
  • X 平行于轴 移动 -D 。
  • Y 平行于轴 移动 +D 。
  • Y 平行于轴 移动 -D 。

这些举动都不只是 以概率 1/4 选择。

您最初处于起点并且刚刚 N 我想一跳到达目标。

输出实现目标的概率。


入力

输入将以以下格式从标准输入提供。

N D
X Y
  • 1 行包含一个整数,表示跳转的次数。 N (1 ≦ N ≦ 1,000) 和跳跃距离 D (1 ≦ D ≦ 10^9) 用空格分隔。
  • 2 行包含一个表示目标点坐标的整数。 如果您正确回答 X, Y (-10^9 ≦ X, Y ≦ 10^9) 用空格分隔。

部分点

1 ≦ N ≦ 8 的所有情况,您将得到 如果您正确回答 90 点。 如果您正确回答

1 ≦ N ≦ 30 中的所有案例,您将额外获得 10 点。 如果您正确回答

如果您正确回答所有问题,您将获得奖励积分。 1 点。 如果您正确回答

出力

您最终达到目标的概率 输出为 1 行。还在输出末尾添加换行符。

预期答案的绝对误差或相对误差为10^{-9} 如果答案如下,则视为正确。 随着


入力例1

2 10000000
10000000 10000000

出力例1

0.125

(0, 0) 它们的编号最大为 2 跳跃 飞往 (10000000, 10000000) 的概率为 1/8 。


入力例2

100 2
3 7

出力例2

0.0

跳跃偶数距离无法到达奇数坐标,因此到达奇数坐标的概率为 0 。


入力例3

11 8562174
25686522 17124348

出力例3

0.018174648284912