問題一覧 > 通常問題

No.1377 Half xor Half

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 23
作問者 : leaf_1415leaf_1415 / テスター : wotsushiwotsushi
6 ProblemId : 5307 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-04 04:17:07

問題文

$0$ と $1$ からなる長さ $2N$ の $2$ つの文字列 $S, T$ が与えられます。$S = s_0 s_1 \cdots s_{2N-1}$ とおきます。

あなたは、文字列 $S$ に対して以下の操作を $2N$ 回まで( $0$ 回でもよい)行うことが出来ます。
(操作)

    手順1. $0 \leq x \leq 2N-1$ を満たす整数 $x$ を選ぶ。
    手順2. $0 \leq i \leq N-1$ を満たすすべての整数 $i$ について、 $s_{(x+i)\,\%\,(2N)}$ を $s_{(x+i)\,\%\,(2N)} \oplus s_{(x+i+N)\,\%\,(2N)}$ に置き換える。
ただし、$a\,\%\,b$ は $a$ を $b$ で割った余りを表し、$a \oplus b$ は $(a+b)\,\%\,2$ を表します。

$S$ と $T$ を一致させるための操作の手順を一つ求めて下さい。
ただし、$2N$ 回以内の操作で $S$ と $T$ を一致させることが不可能な場合は、代わりに $-1$ を出力してください。

入力

$N$
$S$
$T$

$1 \leq N \leq 500$
$N$ は整数
$S, T$ は長さ $2N$ の文字列であり、各文字は'0'または'1'である。

出力

$2N$ 回以内の操作で $S$ と $T$ を一致させることが不可能な場合は $-1$ を出力してください。
$2N$ 回以内の操作で $S$ と $T$ を一致させることが可能な場合は、$1$ 行目に操作の回数 $M\, (0 \leq M \leq 2N)$ を出力し、
$2$ 行目から $M+1$ 行目の $M$ 行にわたって、操作の手順を出力してください。
具体的には、$i+1$ 行目に $i$ 回目の操作の手順1.で選択する $x$ を出力してください。
答えが複数ある場合はどれを出力しても正解となります。
最後に改行してください。

サンプル

サンプル1
入力
4
10101001
10011011
出力
2
6
0

$1$ 回目の操作で $x=6$ とすることで、$S = 00101011$ となります。
さらに $2$ 回目の操作で $x=0$ とすることで、$S = 10011011$ となって $S$ と $T$ が一致します。

サンプル2
入力
5
1101001100
1000111010
出力
-1

$2N$ 回以内の操作で $S$ と $T$ を一致させることが不可能な場合は $-1$ を出力してください。

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