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. Additionally, Luca sees the terminal and thus he knows which shell's input string was affected when he presses a key.
His keyboard has keys with distinct characters on them and Backspace. When a character key press goes to a shell, the character is simply 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 the Backspace went there). Each key press has probability of going to the left shell and probability of going to the right one.
Luca wants to type some fixed string consisting of distinct characters in both shells. He has already managed to type correct characters to the left shell and to the right one (i.e. the strings in the two shells are и ). For example, consider , (the string could be ab), and . A possible sequence of events is:
Step
Key
Side
Left shell
Right shell
0
-
-
a
1
b
Right
ab
2
a
aba
3
Left
a
4
b
Right
abab
5
Backspace
aba
6
Left
-
7
8
Right
ab
9
a
Left
a
10
b
Right
abb
11
Left
ab
12
Backspace
Right
ab
In total, typing ab to both shells took key presses.
Let us define an incorrect character like so: a character in one of the two shells, which needs to be deleted at some point before typing the full string (and only that) to both shells. Luca has decided that he will never press Backspace, if there is no incorrect character in at least one of the shells. He has also decided that he will never press a key which will always result in an incorrect character. Luca is wondering what his optimal strategy would be under these constraints. In particular, he wants to know what is the minimum expected (average) number of key presses. Help Luca by writing a program fork.cpp which solves this problem.
输入格式
From the first and only line of the standard input, your program should read , , and .
输出格式
On the first and only line of the standard output, your program should print the computed answer to (preferably) digits of precision or more. You can use: std::cout << std::setprecision(12) << ans << std::endl;
样例
样例输入 1
0.3 2 0 1
样例输出 1
16.7142857142857
数据范围与提示
Constraints
Subtasks and scoring
Subtask
Points
To get the points for a given subtask, your solution must successfully pass all tests in it and in all previous subtasks. To pass a test, your solution must print an answer with a relative error at most , i.e.:
