Marina and Vasya

time limit per test 1 second

memory limit per test 256 megabytes

input standard input

output standard output

Marina loves strings of the same length and Vasya loves when there is a third string, different from them in exactlytcharacters. Help Vasya find at least one such string.

More formally, you are given two stringss1,s2of lengthnand numbert. Let's denote asf(a, b)the number of characters in which stringsaandbare different. Then your task will be to find any strings3of lengthn, such thatf(s1, s3) = f(s2, s3) = t. If there is no such string, print - 1.

Input

The first line contains two integersnandt(1 ≤ n ≤ 105,0 ≤ t ≤ n).

The second line contains strings1of lengthn, consisting of lowercase English letters.

The third line contain strings2of lengthn, consisting of lowercase English letters.

Output

Print a string of lengthn, differing from strings1and froms2in exactlytcharacters. Your string should consist only from lowercase English letters. If such string doesn't exist, print -1.

Sample test(s)

input

3 2
abc
xyc

output

ayd

input

1 0
c
b

output

-1

建设性设计问题：

　　　　创造不同即是创造相同：t = n - t;

　　　　首先考虑ch1和ch2相同的字母，如果这样的字母能够满足要求，则结束；

　　　　如果还不够，再考虑ch1和ch2中不同的字母，不同ans即为一个像ch1，一个像ch2；

　　　　如果还不够，则无解；

　　　　想要相同很简单，赋值即可，想要不同就拿'a','b','c'去比较ch1和ch2的字母，总有都不一样的，赋值也即可；

　　　　如上所说，开始先记录相同数目x，和不同数目y，x+y/2即为最大相同值，若t>x+y/2显然无解；

　　　　若有解，先判断相同数目x能否满足要求，tt = t - x;若tt <= 0 则表示满足，tt = 0;反而在相同字母都兑换的情况下t = x，搞不同的字母，ch1一个(sign = 1) and ch2一个(sign = 0),同时tt--;就ok了；

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
const int maxn = 1e5+5;
using namespace std;
char ch1[maxn];
char ch2[maxn];
char ans[maxn];
bool flag[maxn];
int main(){
    int n,t;
    int x = 0,y = 0;
    bool sign = 0;
    scanf("%d%d",&n,&t);
    t = n - t;
    scanf("%s%s",ch1,ch2);
    for(int i = 0; i < n; i++){
        if(ch1[i] == ch2[i]){
            flag[i] = 1;
            x++;
        }
        else y++;
    }
    if(t > x+y/2){
        puts("-1");
        return 0;
    }
    else {
        int tt = t - x;
        if(tt < 0)tt= 0;
        else t = x;
        for(int i = 0; i < n; i++){
            if(flag[i] && t){
                ans[i] = ch1[i];
                t--;
            }
            else if(tt||sign){
                if(sign){
                    sign = 0;
                    ans[i] = ch2[i];
                }
                else {
                    tt--;
                    ans[i] = ch1[i];
                    sign = 1;
                }
            }
            else {
                for(int j = 0; j < 3; j++){
                    if(ch1[i] != 'a'+j && ch2[i] != 'a'+j){
                        ans[i] = 'a'+j;
                        break;
                    }
                }//！！！有选择恐惧症的我一直在纠结不同的话该放什么字母上去，这是姿势。。
            }
        }
    }
    ans[n] = '\0';
    cout<< ans<< endl;
    return 0;
}

优质内容筛选与推荐>>
1、理直气和
2、wep密钥的长度
3、iOS 从各种效果图颜色标注生成 UIColor
4、Atitit 衡量项目的规模
5、Flash快捷键积累:

0 │ 收藏 │ 举报

Marina and Vasya

朋友将在看一看看到

分享想法到看一看