No.1377 Half xor Half
Problem Statement
You are given $2$ strings $S, T$ of length $2N$ consisting of $0$ and $1$. Let $S = s_0 s_1 \cdots s_{2N-1}$.
You can perform the following operation on the string $S$ up to $2N$ times (possibly $0$ times).
(Operation)
-
Step 1. Choose an integer $x$ satisfying $0 \leq x \leq 2N-1$.
Step 2. For every integer $i$ satisfying $0 \leq i \leq N-1$, replace $s_{(x+i)\,\%\,(2N)}$ with $s_{(x+i)\,\%\,(2N)} \oplus s_{(x+i+N)\,\%\,(2N)}$.
Find one sequence of operations that makes $S$ and $T$ equal.
However, if it is impossible to make $S$ and $T$ equal within $2N$ operations, output $-1$ instead.
Input
$N$ $S$ $T$
$1 \leq N \leq 500$
$N$ is an integer
$S, T$ are strings of length $2N$, and each character is '0' or '1'.
Output
If it is impossible to make $S$ and $T$ equal within $2N$ operations, output $-1$.
If it is possible to make $S$ and $T$ equal within $2N$ operations, output the number of operations $M\, (0 \leq M \leq 2N)$ on line $1$,
and output the sequence of operations on the $M$ lines from line $2$ to line $M+1$.
Specifically, on line $i+1$, output the $x$ chosen in Step 1 of the $i$-th operation.
If there are multiple answers, any of them will be accepted.
Print a newline at the end.
Sample
Sample 1
Input
4 10101001 10011011
Output
2 6 0
Choosing $x=6$ in the $1$-st operation gives $S = 00101011$.
Then, choosing $x=0$ in the $2$-nd operation gives $S = 10011011$, and $S$ and $T$ become equal.
Sample 2
Input
5 1101001100 1000111010
Output
-1
If it is impossible to make $S$ and $T$ equal within $2N$ operations, output $-1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
leaf_1415
wotsushi