410419: GYM104020 C Crashing Competition Computer

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Crashing Competition Computertime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are writing code for a hackathon where you need to decode Binary ALGOL Punch Cards. You have already come up with the optimal solution and only need to type it out. The solution consists of $$$c$$$ characters, and your typing speed is $$$1$$$ character per time unit. However, your computer is prone to sudden crashes: after every character you type there is a probability of $$$p$$$ that your computer crashes and you need to start over again. Recovering after a crash costs $$$r$$$ time units, and you can then continue typing from the last point where you saved your code.

You can click "Save" at any time (which costs $$$t$$$ time units) to save your code and to be able to restart from this point after crashes. Clicking "Save" will not cause your computer to crash.

Determine how many (expected) time units you need to complete the code. Note that the code should be saved after typing the last character.

Input

The input consists of:

  • One line with three integers $$$c$$$, $$$t$$$, and $$$r$$$ ($$$1 \leq c \leq 2000$$$, $$$0 \leq t, r \leq 10^9$$$), indicating the number of characters, the time cost of clicking "Save", and the time cost of recovering after a crash.
  • One line with a floating-point number $$$p$$$ ($$$0.001 \leq p \leq 0.999$$$, with at most $$$10$$$ digits after the decimal point), the probability that your computer crashes after a character press.
Output

Output the expected number of time units you need to complete the code.

Your answer should have an absolute or relative error of at most $$$10^{-6}$$$.

ExamplesInput
2 1 5
0.25
Output
8.00000000000000000000
Input
3 5 2
0.5
Output
26.00000000000000000000
Input
10 4 5
0.327
Output
68.66496735691465991280

加入题单

上一题 下一题 算法标签: