問題一覧 > 通常問題

No.2018 X-Y-X

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 : milkcoffee / テスター : Kiri8128
17 ProblemId : 8006 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-06 16:19:30

問題文

A と B からなる長さ NN の文字列 SS 及び TT が与えられます。あなたは、文字列 SS に対して以下の操作を 00 回以上何度でも行えます。

  • Si=Si+2S_i = S_{i+2} であるような 1≤i≤N−21 \leq i \leq N-2 を選ぶ。そして、 Si+1S_{i+1} の文字を変更する(AならばBに、BならばAにする)。

SS を TT に一致させることはできますか。できる場合は必要な最小の操作回数を求めてください。

入力

NN
SS
TT

  • 3≤N≤2×1053 \leq N \leq 2 \times 10^5
  • NN は整数
  • S,TS,T は A,B からなる長さ NN の文字列

出力

SS を TT に一致させることができる場合、必要な最小の操作回数を出力してください。
一致させることが不可能な場合は -1 を出力してください。

サンプル

サンプル1
入力
4
ABAA
AABA
出力
2

まず、 i=1i=1 として操作をすると、 SS は AAAA となります。
次に、 i=2i=2 として操作をすると、 SS は AABA となります。

サンプル2
入力
4
BBAA
BABA
出力
-1

SS に対して操作をすることができないため、 SS を TT に一致させることはできません。

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