問題一覧 > 通常問題

No.1377 Half xor Half

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 33
作問者 : leaf_1415 / テスター : wotsushi
お気に入りにしたユーザー ProblemId : 5307 / 自分の提出
問題文最終更新日: 2021-02-04 04:17:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 281 (順位表) の他の問題:

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)}$.
Here, $a\,\%\,b$ denotes the remainder when $a$ is divided by $b$, and $a \oplus b$ denotes $(a+b)\,\%\,2$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。