← 返回题目列表

Codeforces · 24/D

D. 坏掉的机器人

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

您收到了一个在矩形板上行走的非常聪明的机器人作为礼物。不幸的是,您知道它已损坏并且行为相当奇怪(随机)。棋盘由 N 行和 M 列的单元格组成。机器人最初位于第 i 行第 j 列的某个单元格。然后,机器人每走一步都可以前往另一个单元格。目标是到达最底部(第 N 行)。机器人可以停留在当前单元格、向左移动、向右移动或移动到当前单元格下方。如果机器人位于最左列,则无法向左移动;如果机器人位于最右列,则无法向右移动。在每一步中,所有可能的行动都是同样可能的。返回到达最底行的预期步数。

输入

在第一行,您将得到两个空格分隔的整数 N 和 M (1 ≤ N, M ≤ 1000)。在第二行,您将获得另外两个空格分隔的整数 i 和 j (1 ≤ i ≤ N, 1 ≤ j ≤ M) — 初始行的编号和初始列的编号。请注意,(1, 1) 是棋盘的左上角,(N, M) 是右下角。

输出

在一行中输出期望的步数,小数点后至少有 4 位数字。

示例

输入 #1

10 10
10 4

输出 #1

0.0000000000

输入 #2

10 14
5 14

输出 #2

18.0038068653