Kattis 스피드런

Joshua의 2024년 새해 결심은 한 해가 끝나기 전에 Kattis 플랫폼에 있는 모든 문제의 절반을 푸는 것이었다. 한 해가 저물어 가면서, 그는 목표를 달성하려면 자신이 아는 모든 전략을 사용해야 한다는 것을 깨닫는다. 지금까지 그는 Kattis에서 다른 사람들이 만든 문제만 풀었다. 하지만 그는 직접 문제를 만들고 업로드한 뒤 풀 수도 있다. 이 방법은 다른 사람의 문제를 푸는 것보다 일이 적을 수도 있지만, 전체 문제 수도 증가시킨다.

현재 Kattis에는 $P$개의 문제가 있으며, Joshua는 그중 $S$개를 풀었다. 그는 다음 행동을 할 수 있다:

• 문제 하나를 푼다. 이 행동에는 $A$초가 걸리고 $S$가 1만큼 증가한다.

• 새 문제 하나를 작성한다. 이 행동에는 $B$초가 걸리고 $P$와 $S$가 모두 1만큼 증가한다.

Joshua가 시간을 최적으로 사용한다면, $\frac{S}{P} > 0.5$이 되도록 $S$와 $P$를 증가시키는 데 몇 초가 걸리는가?

채점

여러 테스트 그룹으로 이루어진 테스트 세트로 제출한 답을 평가하며, 각 테스트 그룹에는 일정한 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스로 이루어진다. 한 테스트 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$12$| $A=1, B=10^5$

$2$ |$18$| $B=1, A=10^5$

$3$ |$20$| $S, P \leq 1000$

$4$ |$50$| 추가 제한 조건이 없다.

입력의 첫째 줄에는 Joshua가 지금까지 푼 문제의 수인 정수 $S$ ($0 \leq S \leq 10^5$)가 주어진다.

둘째 줄에는 현재 Kattis에 있는 전체 문제의 수인 정수 $P$ ($1 \leq P \leq 10^5$)가 주어진다. $S < \frac{P}{2}$임이 보장된다.

셋째 줄에는 문제 하나를 푸는 데 걸리는 시간인 정수 $A$ ($1 \leq A \leq 10^5$)가 주어진다.

넷째 줄에는 새 문제 하나를 만드는 데 걸리는 시간인 정수 $B$ ($1 \leq B \leq 10^5$)가 주어진다.

일부 테스트 케이스에서는 $A$가 $B$보다 훨씬 클 수 있으며, 다른 테스트 케이스에서는 $B$가 $A$보다 훨씬 클 수 있음에 유의하라.

Joshua가 Kattis에 있는 모든 문제의 절반보다 엄격히 많은 문제를 푸는 데 걸리는 최소 초 수를 정수로 출력한다.

예제 1에서는 문제를 푸는 것은 매우 빠르지만, 새 문제를 만드는 데는 매우 오랜 시간이 걸린다. 최적의 전략은 문제만 푸는 것이다. 절반보다 많은 문제를 풀려면 $51$개의 문제를 풀어야 한다. $A=1$이므로 답은 $51$이다.

예제 2에서 Joshua가 절반보다 많은 문제를 풀려면 2개의 문제를 풀어야 한다.

예제 3에서 최적의 전략은 11개의 문제를 풀고 1개의 문제를 만드는 것이다. 여기에는 총 $11 \cdot 7 + 1 \cdot 6 = 83$초가 걸린다. 이보다 빠른 다른 전략은 없다.