I - Circular Shift on PDCA-Cycle

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)


配点:300300

問題文

P, D, C, A のみからなる文字列を PDCA-String と呼びます.

さらに,PDCA-String XX が以下の条件を満たすとき,またそのときに限って XXPDCA-Cyclic であるといいます:

  • XX の長さ 22 の連続部分列はすべて PD, DC, CA, AP のいずれかである.

たとえば 33 PDCA-String DCAPDCAPDCAPDCA, A, DCA はいずれも PDCA-Cyclic です.

長さ NN の PDCA-String SS があります.

また,次の操作を 00 回以上何度でも行えます:

  • 1kN1 \leq k \leq N なる整数 kk を自由に選び,SS11 文字目から kk 文字目までを 11 要素分だけ左に循環シフトする.すなわち,SSS=(S2,S3,,Sk1,Sk,S1,Sk+1,Sk+2,,SN)S' = (S_2, S_3, \ldots, S_{k-1}, S_k, S_1, S_{k+1}, S_{k+2}, \dots, S_N) によって定められる文字列 S=(S1,S2,,SN)S' = (S'_1, S'_2, \ldots, S'_N) で置き換える.

SS が PDCA-Cyclic であるようにすることが目標です.
この目標が達成可能か判定し,できるならばそのために必要な操作回数の最小値を求めてください.

制約

  • 1Φ1051 \leq \Phi \leq 10^5
  • 1N101 \leq N \leq 10
  • NN は整数
  • SS は長さ NN の PDCA-String

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NN
SS

出力

有限回の操作によって目標を達成できるならば,操作を行う回数の最小値を出力せよ.
どのように操作を行っても目標を達成できないならば -1 と出力せよ.

サンプル

入力例1
1
5
ACDPP
出力例1
3

たとえば次のようにして 33 回の操作で目標を達成できます:

  • 1 ⁣:k=41 \colon k = 4として操作を行う.
    • S=S = CDPAP となる.
  • 2 ⁣:k=32 \colon k = 3 として操作を行う.
    • S=S = DPCAP となる.
  • 2 ⁣:k=22 \colon k = 2 として操作を行う.
    • S=S = PDCAP となる.
    • このとき SS は PDCA-Cyclic である.

どのようにしても 33 回未満の操作では目標を達成できないので,33 が答えです.


入力例2
5
6
CAPDCA
3
PCD
5
DACAP
4
PPAP
1
C
出力例2
0
2
3
-1
0

提出


Go (1.21)