D - 大ジャンプ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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