E - Card Battle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君と青木君がカードバトルで対戦しています。

各プレイヤーは「エネルギー」というパラメータを持っています。高橋君の初期エネルギーは H、青木君の初期エネルギーは A です。

バトルはターン制で進行し、最大 T ターン行われます。各ターンにおいて、高橋君と青木君はそれぞれ以下の行動のいずれかを選択し、両者の行動の効果を同時に適用します：

  • チャージ：自分のエネルギーを 1 増加させる。
  • アタック：自分のエネルギーを 1 減少させ、相手のエネルギーを 1 減少させる。ただし、アタックを選択するには、そのターン開始時点で自分のエネルギーが 1 以上でなければならない。

各ターンの処理は以下の手順で行われます：

  1. 両者が行動を選択する。
  2. 両者の行動の効果を同時に適用し、エネルギーを更新する。
  3. 更新後のエネルギーに基づき、以下の判定を行う：
  • 青木君のエネルギーが 0 以下で、かつ高橋君のエネルギーが 1 以上ならば、高橋君の勝利とし、直ちにバトルは終了する。
  • 両者のエネルギーがともに 0 以下ならば引き分けとし、直ちにバトルは終了する（高橋君の勝利とはみなさない）。
  • 上記のいずれでもなければ、バトルは次のターンに続く。

T ターン終了時点までに上記の終了条件がいずれも満たされなかった場合、バトルは終了し、高橋君の勝利とはみなしません。

青木君はバトル開始前に T ターン分の行動計画を立てています。青木君の行動計画は長さ T の文字列 S で表され、S の i 文字目が C ならば第 i ターンにチャージを、A ならば第 i ターンにアタックを選択することを意味します。青木君はバトルが終了するまで、この計画通りに行動します。なお、入力として与えられる行動計画は、青木君がアタックを選択するターンの開始時点で青木君のエネルギーが 1 以上であることが、高橋君の行動によらず保証されています。

高橋君は青木君の行動計画を事前にすべて把握しており、各ターンの自分の行動を最適に選ぶことができます。

ただし、高橋君には以下の行動制約があります：あるターンの終了時に高橋君のエネルギーが 0 以下になることが許されるのは、そのターンの判定で高橋君の勝利が成立する場合に限ります。それ以外のターンでは、ターン終了時に高橋君のエネルギーが 1 以上でなければなりません。

高橋君が最適に行動したとき、T ターン以内に高橋君の勝利条件を満たせるならば、そのような最も早いターン番号を出力してください。T ターン以内に勝利できない場合は -1 を出力してください。

制約

  • 1 \leq H \leq 5 \times 10^6
  • 1 \leq A \leq 5 \times 10^6
  • 1 \leq T \leq 2 \times 10^6
  • S は長さ T の文字列であり、C と A のみからなる。
  • H, A, T は整数である。
  • 青木君の行動計画において、アタックが指定されたターンの開始時点で青木君のエネルギーが 1 以上であることが、高橋君の行動によらず保証される。

入力

H A T
S
  • 1 行目には、高橋君の初期エネルギーを表す整数 H、青木君の初期エネルギーを表す整数 A、バトルの最大ターン数を表す整数 T が、スペース区切りで与えられる。
  • 2 行目には、青木君の T ターン分の行動計画を表す長さ T の文字列 S が与えられる。S は C と A のみからなる。

出力

高橋君が最適に行動したとき、高橋君の勝利条件を満たせる最も早いターン番号を 1 行で出力せよ。T ターン以内に勝利できない場合は -1 を出力せよ。

入力例 1

3 3 3
AAC

出力例 1

2

入力例 2

1 5 3
CCC

出力例 2

-1

入力例 3

12 15 20
CCACCAACCCCCACCCCCCC

出力例 3

-1

入力例 4

30 50 60
CCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCA

出力例 4

-1

入力例 5

1 1 1
A

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi and Aoki are playing a card battle.

Each player has a parameter called "energy". Takahashi's initial energy is H, and Aoki's initial energy is A.

The battle proceeds in turns, lasting for at most T turns. In each turn, Takahashi and Aoki each choose one of the following actions, and the effects of both actions are applied simultaneously:

  • Charge: Increase one's own energy by 1.
  • Attack: Decrease one's own energy by 1 and decrease the opponent's energy by 1. However, to choose Attack, the player's energy must be at least 1 at the beginning of that turn.

The process of each turn is performed in the following steps:

  1. Both players choose their actions.
  2. The effects of both actions are applied simultaneously to update their energies.
  3. Based on the updated energies, the following judgment is made:
  • If Aoki's energy is 0 or less, and Takahashi's energy is 1 or more, Takahashi wins, and the battle ends immediately.
  • If both players' energies are 0 or less, it is a draw, and the battle ends immediately (this is not considered a victory for Takahashi).
  • If neither of the above conditions is met, the battle continues to the next turn.

If none of the ending conditions are met by the end of the T-th turn, the battle ends, and it is not considered a victory for Takahashi.

Before the battle begins, Aoki has made an action plan for T turns. Aoki's action plan is represented by a string S of length T, where the i-th character of S is C if he chooses Charge in the i-th turn, and A if he chooses Attack in the i-th turn. Aoki will follow this plan until the battle ends. Note that the action plan given as input guarantees that at the start of any turn where Aoki chooses Attack, Aoki's energy is at least 1, regardless of Takahashi's actions.

Takahashi knows Aoki's action plan in advance and can choose his actions optimally in each turn.

However, Takahashi has the following constraint on his actions: Takahashi's energy is allowed to become 0 or less at the end of a turn *only if* Takahashi's victory is established in that turn's judgment. In any other turn, Takahashi's energy must be at least 1 at the end of the turn.

If Takahashi plays optimally, output the earliest turn number in which he can satisfy the victory condition within T turns. If he cannot win within T turns, output -1.

Constraints

  • 1 \leq H \leq 5 \times 10^6
  • 1 \leq A \leq 5 \times 10^6
  • 1 \leq T \leq 2 \times 10^6
  • S is a string of length T consisting only of C and A.
  • H, A, T are integers.
  • In Aoki's action plan, it is guaranteed that at the start of any turn where Attack is specified, Aoki's energy is at least 1, regardless of Takahashi's actions.

Input

H A T
S
  • The first line contains three space-separated integers: H, representing Takahashi's initial energy; A, representing Aoki's initial energy; and T, representing the maximum number of turns in the battle.
  • The second line contains a string S of length T representing Aoki's action plan for T turns. S consists only of C and A.

Output

If Takahashi plays optimally, print the earliest turn number in which he can satisfy the victory condition in a single line. If he cannot win within T turns, print -1.

Sample Input 1

3 3 3
AAC

Sample Output 1

2

Sample Input 2

1 5 3
CCC

Sample Output 2

-1

Sample Input 3

12 15 20
CCACCAACCCCCACCCCCCC

Sample Output 3

-1

Sample Input 4

30 50 60
CCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCACCCCCA

Sample Output 4

-1

Sample Input 5

1 1 1
A

Sample Output 5

1