問題一覧 > 通常問題

No.2076 Concon Substrings (ConVersion)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : AngrySadEightAngrySadEight / テスター : nok0nok0
1 ProblemId : 8362 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-16 16:55:36

問題文

英小文字からなる長さ $N$ の文字列 $S$ が与えられます.これから,次に示す操作を行うことができます.

  • 奇数回目の操作では,$S$ の連続する部分列の中で con が $A$ 回連続して続く箇所をひとつ選び,coon に変える. $S$ の連続する部分列に con が $A$ 回連続して続く箇所が無いときは,この操作は行えない.
  • 偶数回目の操作では,$S$ の連続する部分列の中で con が $B$ 回連続して続く箇所をひとつ選び,coon に変える. $S$ の連続する部分列に con が $B$ 回連続して続く箇所が無いときは,この操作は行えない.

操作を行うことのできる回数の最大値を求めてください.

入力

$N$ $A$ $B$
$S$

  • $N, A, B$ は整数である.
  • $1 \leq N \leq 5 \times 10^4$
  • $1 \leq A,B \leq N$
  • $S$ は英小文字からなる長さ $N$ の文字列である.

出力

答えを出力せよ.

サンプル

サンプル1
入力
7 1 2
contest
出力
1

contestcoontest と操作することで, $1$ 回操作できます.$2$ 回以上操作を行うことはできないため,答えは $1$ です.

サンプル2
入力
15 1 2
confoxconconfox
出力
2

confoxconconfoxcoonfoxconconfoxcoonfoxcoonfox と操作することで, $2$ 回操作できます.$3$ 回以上操作を行うことはできないため,答えは $2$ です.

サンプル3
入力
19 1 1
kudamakitsukasacoon
出力
0

元から一度も操作を行うことができません.

サンプル4
入力
21 2 3
conconconconconconcon
出力
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。