問題一覧 > 通常問題

No.2076 Concon Substrings (ConVersion)

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

問題文

英小文字からなる長さ NN の文字列 SS が与えられます．これから，次に示す操作を行うことができます．

  • 奇数回目の操作では，SS の連続する部分列の中で con が AA 回連続して続く箇所をひとつ選び，coon に変える． SS の連続する部分列に con が AA 回連続して続く箇所が無いときは，この操作は行えない．
  • 偶数回目の操作では，SS の連続する部分列の中で con が BB 回連続して続く箇所をひとつ選び，coon に変える． SS の連続する部分列に con が BB 回連続して続く箇所が無いときは，この操作は行えない．

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

入力

NN AA BB
SS

  • N,A,BN, A, B は整数である．
  • 1≤N≤5×1041 \leq N \leq 5 \times 10^4
  • 1≤A,B≤N1 \leq A,B \leq N
  • SS は英小文字からなる長さ NN の文字列である．

出力

答えを出力せよ．

サンプル

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

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

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

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

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

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

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

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