Overview

In this problem, given Aoki’s predetermined actions, Takahashi must optimally choose either “Charge” or “Attack” in each turn to win in the minimum number of turns (or determine that winning is impossible).

By formulating the transition of both players’ energy in each turn focusing on the total number of “Attacks” Takahashi has made so far, and transitioning states in a dynamic programming (DP) like manner, we can solve this problem in \(O(T)\) time.

---

Analysis

1. Formulating the State (Focusing on the Number of Attacks \(m\))

In each turn, Takahashi can choose either “Charge” or “Attack”. Since Aoki’s actions are fixed, Takahashi’s degree of freedom lies in “which action to choose in each turn”.

Let \(m\) be the total number of times Takahashi has chosen “Attack” by the end of the \(k\)-th turn. Let us express the energy of both players at the end of the \(k\)-th turn using \(m\).

From Aoki’s action plan, let \(Y_k\) be the number of times Aoki has attacked by the \(k\)-th turn (the number of As in the first \(k\) characters of the string \(S\)).

• Aoki’s energy at the end of the \(k\)-th turn, \(P_k(m)\) Aoki charges \(k - Y_k\) times and attacks \(Y_k\) times. Additionally, he is attacked by Takahashi \(m\) times. $\(P_k(m) = A + (k - Y_k) - Y_k - m = A + k - 2Y_k - m\)\( Here, if we let \)P_{\text{base}} = A + k - 2Y_k\( be Aoki's energy if Takahashi had never attacked, the actual energy can be expressed as follows: \)\(P_k(m) = P_{\text{base}} - m\)$

• Takahashi’s energy at the end of the \(k\)-th turn, \(Q_k(m)\) Takahashi charges \(k - m\) times and attacks \(m\) times. Additionally, he is attacked by Aoki \(Y_k\) times. $\(Q_k(m) = H + (k - m) - m - Y_k = H + k - Y_k - 2m\)\( Here, if we let \)Q_{\text{base}} = H + k - Y_k\( be Takahashi's energy if Takahashi had never attacked, the actual energy can be expressed as follows: \)\(Q_k(m) = Q_{\text{base}} - 2m\)$

Thus, the energy of both players at the end of the \(k\)-th turn is uniquely determined solely by Takahashi’s cumulative number of attacks \(m\).

---

2. Formulating Survival and Victory Conditions as Inequalities

We can organize the conditions that must be satisfied at the end of each turn as inequalities in terms of the number of attacks \(m\).

① Conditions to “Win” on the \(k\)-th Turn

For Takahashi to win, the following two conditions must be satisfied simultaneously: - Aoki’s energy is \(0\) or less: $\(P_k(m) \le 0 \iff P_{\text{base}} - m \le 0 \iff m \ge P_{\text{base}}\)\( - Takahashi's energy is \)1\( or more: \)\(Q_k(m) \ge 1 \iff Q_{\text{base}} - 2m \ge 1 \iff m \le \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\)$

Therefore, the condition for the number of attacks \(m\) required for victory is \(P_{\text{base}} \le m \le \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\) (and \(m \ge 0\)).

② Conditions to “Survive and Proceed to the Next Turn” on the \(k\)-th Turn

To proceed to the next turn without winning, both players’ energy must be \(1\) or more. - Aoki’s energy is \(1\) or more: $\(P_k(m) \ge 1 \iff m \le P_{\text{base}} - 1\)\( - Takahashi's energy is \)1\( or more: \)\(Q_k(m) \ge 1 \iff m \le \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\)$

Therefore, if we define the upper limit of \(m\) allowed to proceed to the next turn as \(U_{\text{next}}\), $\(U_{\text{next}} = \min\left(P_{\text{base}} - 1, \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\right)\)\( we must satisfy \)0 \le m \le U_{\text{next}}$.

---

3. Dynamically Updating the Maximum Number of Attacks \(M\)

To survive (or win) at the end of the \(k\)-th turn, we maintain the maximum achievable number of attacks \(m\), denoted as \(M\).

Let \(M_{k-1}\) be the maximum number of attacks with which Takahashi could survive at the end of the \((k-1)\)-th turn. In the \(k\)-th turn, Takahashi can choose to “Attack” or “not Attack”. - Since he survived the previous turn (i.e., his energy was \(1\) or more), it is possible to choose to attack at the start of the \(k\)-th turn. - Therefore, the maximum achievable number of attacks (as a candidate) at the end of the \(k\)-th turn becomes \(M_{k-1} + 1\).

Using this, we perform the following process every turn:

• Victory Check: The maximum number of attacks Takahashi can perform while surviving is \(M_{\text{win}} = \min\left(M_{k-1} + 1, \left\lfloor \frac{Q_{\text{base}} - 1}{2} \right\rfloor\right)\). If this is at least the number of attacks \(P_{\text{base}}\) required to defeat Aoki (and \(M_{\text{win}} \ge 0\)), then victory is possible on the \(k\)-th turn.
• Survival Update: If we proceed to the next turn, we restrict the maximum number of attacks by the survival condition and update it to \(M_k = \min(M_{k-1} + 1, U_{\text{next}})\). If \(U_{\text{next}} < 0\) or \(M_k < 0\), it is impossible to survive any further and continue the game.

---

Algorithm

1. Initialize variables:
   • P (\(P_{\text{base}}\)): Aoki’s initial energy \(A\)
   • Q (\(Q_{\text{base}}\)): Takahashi’s initial energy \(H\)
   • M: The maximum achievable number of attacks, initially \(0\)
2. For \(k = 1, 2, \dots, T\), perform the following loop:
   • Update P and Q based on Aoki’s action \(y\) (\(1\) if A, \(0\) if C).
     • P = P + 1 - 2 * y
     • Q = Q + 1 - y
   • Calculate the upper limit for Takahashi’s survival \(U_{\text{win}} = \lfloor (Q - 1) / 2 \rfloor\).
   • Calculate the maximum number of attacks for victory \(M_{\text{win}} = \min(M + 1, U_{\text{win}})\).
   • Victory Check: If \(M_{\text{win}} \ge P\) and \(M_{\text{win}} \ge 0\), output the turn number \(k\) and terminate.
   • Survival Update: Calculate the upper limit to proceed to the next turn \(U_{\text{next}} = \min(P - 1, U_{\text{win}})\), and update the maximum number of attacks to M = min(M + 1, U_next).
   • If U_next < 0 or M < 0, we cannot proceed further, so break out of the loop.
3. If the loop ends without victory, output -1.

---

Complexity

• Time Complexity: \(O(T)\) This is a single loop over the number of turns \(T\). Since each operation inside the loop runs in constant time \(O(1)\), it executes very quickly.
• Space Complexity: \(O(T)\) or \(O(1)\) Only \(O(T)\) space is used to store the input string \(S\).

---

Implementation Points

Floor Division for Negative Numbers (Floor Function)

Integer division / in C++ rounds towards zero for negative numbers (e.g., -1 / 2 becomes 0). However, \(\lfloor (Q - 1) / 2 \rfloor\) in the formula must be a floor function (rounding towards negative infinity) (e.g., \(\lfloor -1 / 2 \rfloor = -1\)).

To handle this correctly, we can use a function like the following to ensure correct downward rounding even for negative numbers.

long long floor_div2(long long x) {
    return x >= 0 ? x / 2 : (x - 1) / 2;
}

Source Code

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// 負の数にも対応した床関数 (x / 2 の床関数)
long long floor_div2(long long x) {
    return x >= 0 ? x / 2 : (x - 1) / 2;
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long H, A, T;
    if (!(cin >> H >> A >> T)) return 0;

    string S;
    cin >> S;

    long long P = A;
    long long Q = H;
    long long M = 0;

    for (int k = 1; k <= T; ++k) {
        int y = (S[k - 1] == 'A' ? 1 : 0);
        P = P + 1 - 2 * y;
        Q = Q + 1 - y;

        long long U_win = floor_div2(Q - 1);
        long long M_win = min(M + 1, U_win);

        // 第 k ターンで勝利可能か判定
        if (M_win >= P && M_win >= 0) {
            cout << k << "\n";
            return 0;
        }

        // 次のターンへ進むための更新
        long long U_next = min(P - 1, U_win);
        M = min(M + 1, U_next);

        // 次のターンへ進むことが不可能な場合
        if (U_next < 0 || M < 0) {
            break;
        }
    }

    cout << -1 << "\n";
    return 0;
}

---

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