Summary

Since Aoki’s sequence of actions is fixed, we can determine whether Takahashi can reduce Aoki’s energy to \(0\) or less by each turn by checking how many times Takahashi needs to attack.
By iterating through each turn from the beginning, we can output the first turn where victory becomes possible.

Analysis

First, let us consider the state up to turn \(i\).

• \(c_i\): The number of times Aoki has charged in the first \(i\) turns.
• \(q_i\): Aoki’s energy at the end of turn \(i\) if Takahashi never attacks.

Looking only at Aoki’s own actions, Aoki’s energy:

• Increases by \(+1\) on a charge.
• Decreases by \(-1\) on an attack.

Thus, in the code, we update this value as q.

If Takahashi attacks \(x\) times by turn \(i\), Aoki’s energy decreases by an additional \(x\), so it becomes:

\[ q_i - x \]

Therefore, to reduce Aoki’s energy to \(0\) or less, Takahashi must attack at least:

\[ x \geq q_i \]

times.

In particular, if \(q_i \leq 0\), Aoki’s energy will be \(0\) or less even if Takahashi never attacks.
In this case, Takahashi can always win on this turn because his energy will remain at least \(1\) as long as he only charges.

---

Next, let us consider the case where \(q_i > 0\).

In this case, Takahashi needs to attack at least \(q_i\) times.
Since attacking more than necessary only decreases Takahashi’s energy, it is sufficient to check if he can attack exactly \(q_i\) times.

Let us establish a baseline where Takahashi charges on every turn.

• On turns where Aoki charges: Takahashi’s energy changes by \(+1\).
• On turns where Aoki attacks: Takahashi’s energy changes by \(+1\) but is simultaneously decreased by \(-1\), resulting in a net change of \(0\).

Thus, Takahashi’s energy at the end of turn \(i\) under this baseline is:

\[ H + c_i \]

If Takahashi chooses to “attack” instead of “charge” on a certain turn:

• A charge gives \(+1\).
• An attack gives \(-1\).

Thus, each attack decreases his energy by \(2\) compared to the baseline.

Therefore, Takahashi’s energy after attacking \(x\) times is:

\[ H + c_i - 2x \]

To win, Takahashi’s energy must be at least \(1\). Setting \(x = q_i\), we need:

\[ H + c_i - 2q_i \geq 1 \]

which simplifies to:

\[ 2q_i \leq H - 1 + c_i \]

Additionally, since Takahashi can attack at most \(i\) times during the first \(i\) turns, we also need:

\[ q_i \leq i \]

Consequently, the condition for Takahashi to be able to win at turn \(i\) is either:

\[ q_i \leq 0 \]

or

\[ q_i \leq i \quad \text{and} \quad 2q_i \leq H - 1 + c_i \]

A naive search of all of Takahashi’s possible action sequences would take \(2^T\) time, which is impossible.
Furthermore, DP with energy as a state is also impractical because \(H, A,\) and \(T\) can be extremely large.
In this problem, by comparing the “required number of attacks” and the “possible number of attacks” mathematically, we can determine the feasibility for each turn in \(O(1)\) time.

Algorithm

1. Initialize c = 0. This represents Aoki’s charge count so far.
2. Initialize q = A. This represents Aoki’s energy if Takahashi does not attack.
3. For each turn \(i = 1, 2, \dots, T\), update the state based on Aoki’s action:
   • If it is C, perform c += 1 and q += 1.
   • If it is A, perform q -= 1.
4. Takahashi can win at turn \(i\) if the following condition is satisfied:
   • q <= 0
   • Or q <= i and 2 * q <= H - 1 + c
5. Output the first turn number \(i\) that satisfies the condition.
6. If the condition is never satisfied by the end of the game, output -1.

The check in the code:

if q <= 0 or (q <= i and (q << 1) <= hm1 + c):

directly implements the conditions above.
q << 1 is equivalent to 2 * q.

Complexity

• Time Complexity: \(O(T)\)
• Space Complexity: \(O(T)\)
  Note that excluding the input string \(S\), the auxiliary space complexity is \(O(1)\).

Implementation Points

• Since S is read as bytes, we compare characters with the ASCII code 67 instead of the character 'C'.

  • 67 is the ASCII code for 'C'.

• Although \(T\) is given in the input, it is not explicitly used in the implementation because we can directly use the length of S.

• By precalculating hm1 = H - 1, the conditional expression 2*q <= H - 1 + c is written more concisely.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    H = int(data[0])
    A = int(data[1])
    S = data[3]

    c = 0
    q = A
    hm1 = H - 1

    for i, ch in enumerate(S, 1):
        if ch == 67:  # 'C'
            c += 1
            q += 1
        else:         # 'A'
            q -= 1

        if q <= 0 or (q <= i and (q << 1) <= hm1 + c):
            print(i)
            return

    print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.