ACPC 2020 - Division 1

Start

2020-11-14 10:00 AKST

ACPC 2020 - Division 1

End

2020-11-14 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -10 days 19:21:51

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Best Investing

Geraldine has designed a fantastic investment portfolio that is guaranteed to grow at $r\% $ every year, and she wants to maximize how much she can get out of it. Starting now and for the next $y$ years, she can either deposit money into or withdraw money from her account (but not both) once a year, and after each year the amount in the account grows by $r\% $. Her account stores the dollar amount as a real number.

While she has a good job with flexible hours, Geraldine has bills to pay and she can only work so hard in a given year, so she can only deposit up to $\$ d$ per year. She’ll enjoy the money grown from her wise investing, but she has no use for withdrawing more than $\$ w$ per year.

Given these limits, and given that Geraldine starts with an empty account, what is the maximum net gain that she can earn through her investment?

Note that in the first sample case, Geraldine’s best strategy is to deposit $\$ 1000$ at first, which after one year grows by $5\% $ to $\$ 1050$. At the end of the first and only year she withdraws the full $\$ 1050$. Her net gain is the difference between her total withdrawals ($\$ 1050$) and her total deposits ($\$ 1000$) which in this case is $\$ 50$.

Input

Input begins with a line consisting of the four space-separated integers $r$, $y$, $d$, and $w$ as described in the problem statement, satisfying that

\begin{align*} 1 & \leq r, y \leq 100\\ 1 & \leq d, w \leq 10^6. \end{align*}

Output

Output the maximum net gain that Geraldine can earn with her account. Answers will be accepted up to a relative error of $10^{-6}$ or absolute error of $10^{-2}$, whichever is greater.

Sample Input 1 Sample Output 1
5 1 1000 2000
50
Sample Input 2 Sample Output 2
100 10 1 1000
1513
Sample Input 3 Sample Output 3
7 100 1 100000
13148.3781193723