問題一覧 > 通常問題

No.2076 Concon Substrings (ConVersion)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : 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

contest → coontest と操作することで， $1$ 回操作できます．$2$ 回以上操作を行うことはできないため，答えは $1$ です．

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

confoxconconfox → coonfoxconconfox → coonfoxcoonfox　と操作することで， $2$ 回操作できます．$3$ 回以上操作を行うことはできないため，答えは $2$ です．

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

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

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

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