Problem H
Spaghetti Cutting
After you’ve cooked and served a delicious spaghetti bolognese, your younger sibling exclaims: ”This spaghetti is too long! I will only eat strands that are $A$ micrometers or shorter!”.
The dish has $N$ strands, each $B$ micrometers long. To satisfy your sibling, you will perform $M$ cuts. A strand of length $b$ can be cut in one of $b-1$ possible locations, at positive integer lengths from one of its ends. In each cut you cut one strand in one of its possible locations, uniformly sampled across all locations across all strands. After a cut, the two new strands are placed back in the dish.
Input
The first and only line of input will contain the integers $N$, $M$, $A$, $B$, ($1 \le N \le 10^6$, $1 \le M \le 200$, $1 \le A \le B \le 100$).
Output
Output a single decimal number between $0$ and $N\cdot B$, the expected total length of spaghetti that your sibling will be able to eat. Your answer will be considered correct if it has a relative or absolute error below $10^{-5}$.
Points
Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.
|
Group |
Points |
Constraints |
|
$1$ |
$37$ |
$N = 1$ |
|
$2$ |
$63$ |
No additional constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 2 4 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 1 10 20 |
5.78947368421053 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 1 12 12 |
24 |
| Sample Input 4 | Sample Output 4 |
|---|---|
2 1 1 2 |
2 |
