Fork

Luca opened a Python shell and typed os.fork(), which spawned a second shell. After that, each time Luca pressed any key, it would randomly go to one of the two shells. Each shell has an input string (shown in the terminal), which is edited by the key presses going to that shell. Luca also sees the terminal, so he knows which shell's input string was affected when he presses a key.

His keyboard has $N$ keys with distinct characters on them and Backspace. When a character key press goes to a shell, the character is appended to the end of its input string. When a Backspace key press goes to a shell, the last character of its input string is erased. If the shell's input string is empty, nothing happens to it, though Luca still sees that the Backspace went there. Each key press has probability $P$ of going to the left shell and probability $1 - P$ of going to the right one.

Luca wants to type a fixed string $a_1 a_2 \cdots a_N$ of $N$ distinct characters into both shells. He has already typed $L$ correct characters into the left shell and $R$ into the right one, so the strings in the two shells are $a_1 a_2 \cdots a_L$ and $a_1 a_2 \cdots a_R$.

For example, consider $P = 0.3$, $N = 2$ (the string could be ab), $L = 0$ and $R = 1$. A possible sequence of events is:

In this case, typing ab into both shells took 12 key presses.

An incorrect character is a character in one of the two shells that must be deleted at some point before the full string is typed into both shells. Only such characters count as incorrect.

Luca has decided that he will never press Backspace unless at least one of the shells contains an incorrect character. He has also decided that he will never press a key that always produces an incorrect character. Luca wants the strategy with the minimum expected number of key presses.

Write a program fork.cpp that solves this problem.

The first and only line of standard input contains $P$, $N$, $L$, and $R$.

Print the answer on the first and only line of standard output. Print it with at least 12 digits of precision. You can use:

std::cout << std::setprecision(12) << ans << std::endl;

$0 \le L, R \le N \le 2 \times 10^7$

$0.1 \le P \le 0.9$