Problem C
Kattis Speedrun
Languages
en
sv
Joshua’s New Year’s resolution for 2024 was to solve half of all problems on the Kattis platform before the year ends. As the year draws to a close, he realizes he’ll need to use every strategy he knows to reach his goal. So far, he has only solved others’ problems on Kattis. However, he can also create his own problem, upload it, and solve it. While this might involve less work than solving someone else’s problem, it also increases the total number of problems.
Currently, there are $P$ problems on Kattis, and Joshua has solved $S$ of them. He can take the following actions:
-
Solve a problem. This takes $A$ seconds and increases $S$ by 1.
-
Write a new problem. This takes $B$ seconds and increases both $P$ and $S$ by 1.
If Joshua uses his time optimally, how many seconds will it take for him to increase $S$ and $P$ such that $\frac{S}{P} > 0.5$?
Input
The first line of input contains the integer $S$ ($0 \leq S \leq 10^5$), the number of problems Joshua has solved so far.
The second line contains the integer $P$ ($1 \leq P \leq 10^5$), the total number of problems currently on Kattis. It is guaranteed that $S < \frac{P}{2}$.
The third line contains the integer $A$ ($1 \leq A \leq 10^5$), the time it takes to solve a problem.
The fourth line contains the integer $B$ ($1 \leq B \leq 10^5$), the time it takes to create a new problem.
Note that in some test cases, $A$ may be much larger than $B$, while in others $B$ may be much larger than $A$.
Output
Print an integer: the minimum number of seconds it will take for Joshua to solve strictly more than half of all problems on Kattis.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$12$ |
$A=1, B=10^5$ |
|
$2$ |
$18$ |
$B=1, A=10^5$ |
|
$3$ |
$20$ |
$S, P \leq 1000$ |
|
$4$ |
$50$ |
No additional constraints. |
Explanation of Samples
In sample 1, solving problems is very fast, while creating new problems takes a very long time. The optimal strategy is to only solve problems. To solve more than half, he needs to solve $51$ problems. Since $A=1$, the answer is $51$.
In sample 2, Joshua needs to solve 2 problems to solve more than half.
In sample 3, the optimal strategy is to solve 11 problems and create 1 problem. This takes a total of $11 \cdot 7 + 1 \cdot 6 = 83$ seconds. No other strategy is faster.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 100 1 100000 |
51 |
| Sample Input 2 | Sample Output 2 |
|---|---|
0 3 1 100000 |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 30 7 6 |
83 |
