No.1377 Half xor Half
タグ : / 解いたユーザー数 33
作問者 :
leaf_1415
/ テスター :
wotsushi
問題文
$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)}$ に置き換える。
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。