Overview

In this problem, we simulate a card battle where each player’s actions affect their energy. Given Aoki’s pre-determined action plan, which is known to Takahashi in advance, we need to find the minimum number of turns required for Takahashi to win if he plays optimally.

Focusing on the fact that Aoki’s actions are fixed, we can efficiently find the maximum possible “number of attacks” Takahashi can perform using dynamic programming (DP) or cumulative concepts. This allows us to determine in \(O(1)\) time whether Takahashi can win at each turn, leading to an overall time complexity of \(O(T)\).

---

Analysis

1. Formulating the Energy at the End of Each Turn

Suppose that by the end of turn \(t\), Aoki has performed \(c_t\) charges and \(a_t\) attacks. These values are uniquely determined by the first \(t\) characters of Aoki’s action plan \(S\). On the other hand, suppose Takahashi has performed \(k\) attacks and \(t - k\) charges (\(0 \le k \le t\)).

At this point, the energy of both players, \(H_t\) and \(A_t\), at the end of turn \(t\) can be expressed as follows:

• Aoki’s energy \(A_t\) From the initial value \(A\), it changes by \(+c_t\) due to his own charges, \(-a_t\) due to his own attacks, and \(-k\) due to attacks from Takahashi. $\(A_t = A + c_t - a_t - k\)$

• Takahashi’s energy \(H_t\) From the initial value \(H\), it changes by \(+(t - k)\) due to his own charges, \(-k\) due to his own attacks, and \(-a_t\) due to attacks from Aoki. $\(H_t = H + t - 2k - a_t\)$

2. Conditions for Takahashi to Win at Turn \(t\)

The conditions for Takahashi to win at turn \(t\) are as follows:

1. Aoki’s energy becomes \(0\) or less $\(A_t \le 0 \iff A + c_t - a_t - k \le 0 \iff k \ge A + c_t - a_t\)$
2. Takahashi’s energy is \(1\) or more $\(H_t \ge 1 \iff H + t - 2k - a_t \ge 1 \iff 2k \le H + t - a_t - 1 \iff k \le \left\lfloor \frac{H + t - a_t - 1}{2} \right\rfloor\)$
3. Takahashi’s energy is kept at \(1\) or more at any intermediate turn \(i\) (\(1 \le i < t\)) Letting \(k_i\) be Takahashi’s cumulative number of attacks at each turn \(i\), the following must similarly hold: $\(k_i \le \left\lfloor \frac{H + i - a_i - 1}{2} \right\rfloor\)$

Here, we define Takahashi’s maximum allowable number of attacks at each turn \(i\) as \(M_i = \left\lfloor \frac{H + i - a_i - 1}{2} \right\rfloor\). Since \(a_i + c_i = i\) (the sum of attacks and charges equals the number of turns) in Aoki’s actions, we can rewrite this as: $\(M_i = \left\lfloor \frac{H + i - (i - c_i) - 1}{2} \right\rfloor = \left\lfloor \frac{H - 1 + c_i}{2} \right\rfloor\)\( Surprisingly, **\)M_i\( does not depend on Takahashi's own actions, but is determined solely by Aoki's cumulative number of charges \)c_i$.**

3. Derivation of the Maximum Feasible Number of Attacks \(K_{\max}\)

Let us consider the maximum value \(K_{\max}\) of the cumulative number of attacks \(k_t\) Takahashi can perform up to turn \(t\). Since Takahashi can perform at most \(1\) attack per turn, for any \(i\) (\(0 \le i \le t\)), the following holds: $\(k_t \le k_i + (t - i)\)\( (The maximum occurs when he continuously attacks from turn \)i\( to turn \)t\(). Furthermore, to avoid a game over in the middle, we must have \)k_i \le M_i\( (with \)k_0 = 0, M_0 = 0\(), so: \)\(k_t \le M_i + t - i\)\( must hold for all \)0 \le i \le t\(. Conversely, it is known that the maximum \)kt\( satisfying all of these constraints is indeed constructible. Therefore: \)$K{\max} = \min_{0 \le i \le t} (Mi + t - i) = t + \min{0 \le i \le t} (M_i - i)$$

Letting \(f_i = M_i - i\), we can express this in a very simple form: $\(K_{\max} = t + \min_{0 \le i \le t} f_i\)$

4. Decision Method

At each turn \(t\), if we maintain the minimum value of \(f_i\) (\(0 \le i \le t\)) so far, we can calculate \(K_{\max}\) in \(O(1)\) time. The condition for Takahashi to win at turn \(t\) is: $\(K_{\max} \ge A + c_t - a_t\)\( The minimum \)t$ satisfying this condition will be the answer.

---

Algorithm

1. Initialize the necessary variables:
   • Aoki’s cumulative number of charges c_count \(= 0\), and cumulative number of attacks a_count \(= 0\)
   • The minimum value of \(f_i\) so far, min_f \(= 0\) (since \(f_0 = M_0 - 0 = 0\))
   • The answer ans \(= -1\)
2. Loop \(t\) from \(1\) to \(T\):
   • Increment c_count or a_count depending on Aoki’s action \(S[t-1]\).
   • Calculate \(M_t = \lfloor (H - 1 + c_t) / 2 \rfloor\) (using the bitwise operation (H - 1 + c_count) >> 1 is fast).
   • Calculate \(f_t = M_t - t\), and update min_f with \(\min(\text{min\_f}, f_t)\).
   • Calculate \(K_{\max} = t + \text{min\_f}\).
   • If \(K_{\max} \ge A + c_t - a_t\), Takahashi can win at turn \(t\). Set ans = t and break the loop.
3. After the loop ends, output ans.

---

Complexity

• Time Complexity: \(O(T)\) The processing at each turn \(t\) consists only of constant-time \(O(1)\) arithmetic operations and minimum value updates. Since we perform this at most \(T\) times, the overall time complexity is \(O(T)\), which easily fits within the time limit.

• Space Complexity: \(O(T)\) Since we store the string \(S\) of length \(T\) representing Aoki’s action plan in memory, the space complexity is \(O(T)\).

---

Implementation Points

• Fast Floor Division: The division by \(2\) (rounded down) in the calculation of \(M_t\) can be implemented quickly and concisely using a right bit shift >> 1.

• Setting the Initial Values: Since \(f_0 = 0\), the initial value of min_f must be set to 0. Note that if you set the initial value to infinity (\(\infty\)), it might allow invalid attack transitions where Takahashi’s energy falls to \(0\) or below (i.e., \(k_i > M_i\)) at some intermediate point.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    H = int(data[0])
    A = int(data[1])
    T = int(data[2])
    S = data[3]

    c_count = 0
    a_count = 0
    min_f = 0
    ans = -1

    for t in range(1, T + 1):
        char = S[t - 1]
        if char == "C":
            c_count += 1
        else:
            a_count += 1

        M_t = (H - 1 + c_count) >> 1
        f_t = M_t - t
        if f_t < min_f:
            min_f = f_t

        K_max = t + min_f
        if K_max >= A + c_count - a_count:
            ans = t
            break

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.