Overview

Since Aoki’s action plan \(S\) is fixed, we will determine how many times Takahashi needs to attack by each turn to win.
For each turn \(i\), we compare the “required number of attacks” with the “maximum possible number of attacks” to find the first turn where Takahashi can win.

Analysis

Let us consider the game up to turn \(i\).

Let \(c\) be the number of times Aoki has charged up to this point.
In other words, \(c\) is the number of Cs among the first \(i\) characters of \(S\).

Aoki’s Energy

Aoki’s energy changes as follows:

• He charges \(c\) times, so \(+c\)
• He attacks \(i-c\) times, so \(-(i-c)\)

Therefore, if Takahashi does not attack Aoki even once, Aoki’s energy will be:

\(A + c - (i-c) = A + 2c - i\)

Now, suppose Takahashi attacks \(K\) times up to turn \(i\).
Since each of Takahashi’s attacks reduces Aoki’s energy by \(1\), Aoki’s energy becomes:

\(A + 2c - i - K\)

For Takahashi to win, Aoki’s energy must be \(0\) or less, so:

\(A + 2c - i - K \leq 0\)

which means

\(K \geq A + 2c - i\)

is required.

Thus, the number of attacks Takahashi needs to perform up to turn \(i\) is:

\(A + 2c - i\)

In the code, this is represented as aoki_base.

---

Takahashi’s Energy

Next, suppose Takahashi attacks \(K\) times up to turn \(i\).

Takahashi’s energy changes as follows:

• He charges \(i-K\) times, so \(+(i-K)\)
• He attacks \(K\) times, so \(-K\)
• He receives Aoki’s attacks \(i-c\) times, so \(-(i-c)\)

Thus, Takahashi’s energy is:

\(H + (i-K) - K - (i-c)\)

Simplifying this gives:

\(H + c - 2K\)

For Takahashi to win, his energy must be at least \(1\) at the moment of victory.

Therefore, we need:

\(H + c - 2K \geq 1\)

Rearranging this, we get:

\(2K \leq H + c - 1\)

which means:

\(K \leq \left\lfloor \frac{H+c-1}{2} \right\rfloor\)

Also, naturally, the number of attacks Takahashi can perform up to turn \(i\) is at most \(i\).

Therefore, the maximum possible number of attacks Takahashi can perform up to turn \(i\) is:

\(\min\left(i,\left\lfloor \frac{H+c-1}{2} \right\rfloor\right)\)

In the code, this is represented as max_attack.

---

Winning Condition

To win on turn \(i\), we must have:

• Required number of attacks \(\leq\) Maximum possible number of attacks

In other words, if

\(A + 2c - i \leq \min\left(i,\left\lfloor \frac{H+c-1}{2} \right\rfloor\right)\)

then Takahashi can win by turn \(i\).

We can check the turns sequentially starting from \(1\), and the first turn that satisfies this condition is the answer.

---

Why a Naive Approach is Difficult

Since Takahashi can choose either “charge” or “attack” in each turn, a brute-force search would take up to \(2^T\) possibilities.
Since \(T\) can be up to \(2 \times 10^6\), this is far too slow to pass within the time limit.

Furthermore, even if we consider a DP where the state includes the energies, \(H\) and \(A\) can be as large as \(5 \times 10^6\), leading to an extremely large number of states.

Instead, by only considering the required and possible number of attacks up to each turn, we can solve the problem in \(O(T)\).

Algorithm

1. Set c = 0. This represents the number of times Aoki has charged so far.
2. Iterate through turns \(i=1,2,\dots,T\).
3. If \(S_i\) is C, increment c by \(1\).
4. Calculate the following:
   • aoki_base = A + 2 * c - i
     • The number of attacks Takahashi needs to perform to defeat Aoki.
   • max_attack = min(i, (H + c - 1) / 2)
     • The maximum possible number of attacks Takahashi can perform while keeping his energy at \(1\) or more.
5. If aoki_base <= max_attack, Takahashi can win on this turn, so output \(i\) and terminate.
6. If he cannot win by the end, output -1.

Complexity

• Time Complexity: \(O(T)\)
• Space Complexity: \(O(T)\)

Implementation Details

• Since \(H, A\), and intermediate calculation values can become large, use 64-bit integers (long long in C++).

• c is the “number of times Aoki has charged up to the current turn”.

• Using 1-based indexing for the turn number \(i\) is intuitive because the formula \(A + 2c - i\) can be used as-is.

• If aoki_base is \(0\) or less, it means Aoki’s energy becomes \(0\) or less even if Takahashi does not attack at all. This case is also naturally handled correctly by the condition aoki_base <= max_attack.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long H, A;
    int T;
    cin >> H >> A >> T;

    string S;
    cin >> S;

    long long c = 0;

    for (int i = 1; i <= T; i++) {
        if (S[i - 1] == 'C') c++;

        long long aoki_base = A + 2 * c - i;
        long long max_attack = min<long long>(i, (H + c - 1) / 2);

        if (aoki_base <= max_attack) {
            cout << i << '\n';
            return 0;
        }
    }

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

---

This editorial was generated by gpt-5.5-high.