A. 二进制字符串的费马点

AtCoder Regular Contest 227

二进制字符串的费马点

Fermat Point of Binary Strings

AtCoder

⌀ 614

原题

←B →

二进制字符串的费马点AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

A string of length $2N$ that contains $N$ occurrences of each of 0 and 1 is called a good string.

一个长度为 $2N$ 且恰好包含 $N$ 个 0 和 $N$ 个 1 的字符串称为好字符串。AI (CI翻译)

For good strings $S$ and $T$ , let $\operatorname{dist}(S, T)$ denote the minimum number of swaps required to make $S$ equal to $T$ by swapping two adjacent characters of $S$ zero or more times.

对于好字符串 $S$ 和 $T$ ，令 $\operatorname{dist}(S, T)$ 表示通过将 $S$ 中相邻的两个字符交换零次或多次，使 $S$ 变为 $T$ 所需的最少交换次数。AI (CI翻译)

You are given good strings $A$ , $B$ , and $C$ . Among all good strings $X$ , find one that minimizes the value of

给定好字符串 $A$ 、 $B$ 和 $C$ 。请在所有好字符串 $X$ 中找出一个，使下式的值最小：AI (CI翻译)

[ \operatorname{dist}(A, X)+\operatorname{dist}(B, X)+\operatorname{dist}(C, X), ]

[ \operatorname{dist}(A, X)+\operatorname{dist}(B, X)+\operatorname{dist}(C, X), ]AI (CI翻译)

and output it together with the minimum value.

并输出该字符串及最小值。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$1 \le N \le 2 \times 10^5$
Each of $A$ , $B$ , and $C$ is a good string of length $2N$ .
$N$ is an integer.

$1 \le N \le 2 \times 10^5$
$A$ 、 $B$ 、 $C$ 均为长度为 $2N$ 的好字符串。
$N$ 是整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N
A
B
C

N
A
B
C

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Let $K$ be the minimum value to be found, and let $X$ be a good string that achieves it. Output $K$ and $X$ in the following format:

设要找的最小值为 $K$ ，达到该最小值的好字符串为 $X$ 。请按以下格式输出 $K$ 和 $X$ ：AI (CI翻译)

K
X

K
X

AI (CI翻译)

If multiple outputs satisfy the conditions, you may output any of them.

如果有多个输出满足条件，可以输出其中任意一个。AI (CI翻译)

样例

Input #1

Output #1

4
1010

If we choose `1010` as the good string $X$, then $\operatorname{dist}(A, X)$, $\operatorname{dist}(B, X)$, and $\operatorname{dist}(C, X)$ are $1$, $0$, $3$, respectively, and their sum is $4$. The sum of the distances cannot be made smaller than $4$.

Input #2

Output #2

0
101010

Since the three input strings are all equal, choosing the same string as $X$ makes the sum of the distances $0$.

题目信息

题号

arc227_a

所属比赛

AtCoder Regular Contest 227

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。