CF545B.Equidistant String

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance:

We will define the distance between two strings s and t of the same length consisting of digits zero and one as the number of positions i, such that s__i isn't equal to t__i.

As besides everything else Susie loves symmetry, she wants to find for two strings s and t of length n such string p of length n, that the distance from p to s was equal to the distance from p to t.

It's time for Susie to go to bed, help her find such string p or state that it is impossible.

小苏西喜欢字符串。今天她计算字符串之间的距离。由于苏西毕竟还是个小女孩,她的字符串只包含数字 0 和 1。她使用汉明距离(Hamming distance)的定义:

我们将两个等长字符串 ss 和 tt(均由数字 0 和 1 组成)之间的距离定义为满足 si≠tis_i \ne t_i 的位置 ii 的个数。

此外,由于苏西还特别喜爱对称性,她希望对两个长度为 nn 的字符串 ss 和 tt,找到一个长度同样为 nn 的字符串 pp,使得 pp 到 ss 的距离等于 pp 到 tt 的距离。

现在到了苏西该睡觉的时间了,请你帮她找出这样的字符串 pp,或者说明其不存在。

输入格式

The first line contains string s of length n.

The second line contains string t of length n.

The length of string n is within range from 1 to 105. It is guaranteed that both strings contain only digits zero and one.

第一行包含一个长度为 nn 的字符串 ss。
第二行包含一个长度为 nn 的字符串 tt。
字符串长度 nn 的取值范围为 11 到 10510^5。保证两个字符串仅由数字 0 和 1 组成。

输出格式

Print a string of length n, consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line "impossible" (without the quotes).

If there are multiple possible answers, print any of them.

输出一个长度为 nn 的字符串,该字符串仅由数字 0 和 1 组成,且满足题目要求。如果不存在这样的字符串,则在单独一行中输出 "impossible"(不带引号)。

如果存在多个可能的答案,输出其中任意一个即可。

输入输出样例

  • 输入#1

    0001
    1011

    输出#1

    0011
  • 输入#2

    000
    111

    输出#2

    impossible

说明/提示

In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101.

在第一个样例中,存在多种可能的答案,即:0010、0011、0110、0111、1000、1001、1100、1101。

输入解题思路,AI测评打分。不知道怎么写?

首页