실크의 노래 (강철 영혼)

아래 풀이의 오류 등을 찾았을 경우 디스코드 0prime0으로 연락 주세요.

---

현재 체력을 $h$라고 하자. 최대한의 공격을 버틸 수 있는 전략은 다음과 같다.

• 공격을 받는다. 즉, $h \leftarrow h-A$를 수행한다.
• $h \leq A$이고 실크가 남아있다면 회복한다. 즉,
  1. $h \gt A$가 될 때까지 $h \leftarrow h + B$를 수행한다.
  2. $h \geq H$이면 $h \leftarrow H$를 수행한다.

$H \leq A$인 경우, 한 번의 공격에 즉사하므로 답은 항상 $1$이다.

$H \geq A + B$인 경우, 회복량을 항상 $B$가 되도록 할 수 있다. 따라서 답은 $\left\lceil \frac{H+BS}{A} \right\rceil$이다.

이제 $A \lt H \lt A+B$인 경우만 고려하면 된다.

회복 과정 (1)을 끝낸 후에는 항상 $A \lt h \leq A+B$가 된다는 것에 주목하자. $y=A+B-h$로 정의하면 초기값은 $y_0 = A+B-H$가 되고, 위 전략을 $y$에 대한 식으로 쓰면 아래와 동치이다.

1. $y \leftarrow (y + A) \mod B$
2. $y \leq y_0$이면 $y \leftarrow y_0$

$y \leftarrow y_0$이 수행되면 체력은 초기 상태인 최대 체력으로 돌아온다. 즉, $y = y_0$에서 시작하여 처음으로 $y = y_0$로 돌아올 때까지 $y$값의 변화는 한 주기를 형성한다. 한 주기 동안 받은 공격의 수를 $x$라고 하면, $x$는 $(y_0 + A x) \mod B \leq y_0$를 만족하는 최소의 양의 정수가 된다. 먼저, 다음과 같은 표기법을 정의하자.

$$(L \leq x \leq R) \mod M \Leftrightarrow \begin{cases} x \mod M \in [L \mod M, R \mod M] & (L \mod M \leq R \mod M) \\ x \mod M \in [L \mod M, M) \cup [0, R \mod M] & (L \mod M \gt R \mod M) \\ \end{cases}$$

즉, $x$는 $\left( -y_0 \leq A x \leq 0 \right) \mod B$를 만족하는 최소의 양의 정수이다. $x = 1 + x'$로 쓰면, $x'$는 $\left( -y_0 - A \leq A x \leq -A \right) \mod B$를 만족하는 최소의 음이 아닌 정수이다. 이러한 문제는 $\mathcal{O}(\log B)$에 풀 수 있음이 알려져 있으며, 예를 들어 이 블로그와 같은 글에서 설명하고 있다.

$f(A, M, L, R)$을 $(L \leq A x \leq R) \mod M$을 만족하는 최소의 음이 아닌 정수 $x$로 정의하자. 만약 $(L > R) \mod M$이거나 $L \mod M = 0$이면, $f(A, M, L, R) = 0$이다.

만약 $2(A \mod M) > M$인 경우, 부호를 뒤집어서 $(-R \leq -A x \leq -L) \mod M$을 풀자. 즉, $f(A \mod M,M,L,R) = f(-A \mod M,M,-R,-L)$이다. 그러면 $2(-A \mod M) \leq M$을 만족하게 된다. 따라서 이제부터 항상 $2A \leq M$을 가정할 수 있다.

먼저 자명한 해가 있는지 확인하자. $(L', R') = (L, R) \mod M$으로 두자. 만약 $L' \leq A x \leq R'$을 만족하는 음이 아닌 정수 $x$가 있다면, $x = \left\lceil \frac{L'}{A} \right\rceil$이 해가 된다.

그렇지 않다면, $L' + Mt \leq A x \leq R' + Mt$인 $x$가 존재하는 최소의 음이 아닌 정수 $t$를 찾아야 한다. 이는 $L' \leq Ax - Mt \leq R'$과 동치이고, 이를 $\pmod A$에서 보면 $(L' \leq -Mt \leq R') \mod A$를 만족하는 해를 찾는 것이다. 이렇게 $t$를 찾았으면, $x$는 $L' + Mt \leq Ax$를 만족하는 최소의 음이 아닌 정수이다. 즉, $\displaystyle f(A,M,L,R) = \left\lceil \frac{L + M f(-M,A,L',R')}{A} \right\rceil$이다. 이 관계식으로부터 $f$를 계산할 때 항상 $2A \leq M$을 만족하므로, $\text{mod}$ 값은 $2$배 이상 감소한다. 따라서 $f(A,M,L,R)$의 계산에는 $\mathcal{O}(\log M)$의 시간이 소요된다.

위 방법으로 한 주기 동안 받은 공격 횟수를 계산하면 $x = 1 + f(A, B, -y_0 - A, -A)$이고, 그 동안의 회복 횟수 $N = \left\lceil \frac{Ax}{B} \right\rceil$이다.

$S$를 $N$으로 나눈 몫을 $q$, 나머지를 $r$이라고 하자. 그러면 $q$주기를 반복하면서 $qx$번의 공격을 받고, 나머지 $r$번의 회복은 모두 최댓값인 $B$로 사용할 수 있다. 따라서 답은 $n = qx + \left\lceil \frac{H+Br}{A} \right\rceil$이고, 시간 복잡도는 테스트 케이스당 $\mathcal{O}(\log B)$이다.