http://codeforces.com/gym/101755/problem/M
#include <iostream> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <cstdio> #include <set> #include <map> #include <stack> //#include <tr1/unordered_map> //#include <unordered_map> #include <cmath> //#include<bits/stdc++.h> using namespace std; #define sfi(i) scanf("%d",&i) //#define sfl(i) scanf("%I64d",&i) #define sfs(i) scanf("%s",(i)) #define pri(i) printf("%d\n",i) #define prl(i) printf("%I64d\n",i) #define sff(i) scanf("%lf",&i) #define ll long long #define ull unsigned long long #define uint unsigned int #define mem(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f #define inf 8e19 #define eps 1e-10 #define PI acos(-1.0) #define lowbit(x) ((x)&(-x)) #define fl() printf("flag\n") #define MOD(x) ((x%mod)+mod)%mod #define endl '\n' #define pb push_back #define lson (rt<<1) #define rson (rt<<1|1) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) template<typename T>inline void read(T &x) { x=0; static int p;p=1; static char c;c=getchar(); while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();} x*=p; } //----------------------------------------------- const int maxn=2e5+9; const int mod=1e9+7; string s1,s2,s3; vector<int>vec; int tmp[maxn]; int ans,s_ans[maxn]; void dfs(int pos) { if(pos==vec.size()) { int num1=0,num2=0,num3=0; for(int i=0;i<vec.size();i++) { int id=vec[i]; if(s1[id]-'a'!=tmp[i]) num1++; if(s2[id]-'a'!=tmp[i]) num2++; if(s3[id]-'a'!=tmp[i]) num3++; } if(num1<=1&&num2<=1&&num3<=1) { ans++; for(int i=0;i<pos;i++) s_ans[i]=tmp[i]; } return ; } for(int i=0;i<26;i++) { tmp[pos]=i; dfs(pos+1); } } int main() { //FAST_IO; //freopen("input.txt","r",stdin); while(cin>>s1>>s2>>s3) { vec.clear(); int n=s1.length(); for(int i=0;i<n;i++) { if(s1[i]!=s2[i]||s1[i]!=s3[i]||s2[i]!=s3[i]) { vec.pb(i); } } if(vec.size()>3) { printf("Impossible\n"); continue; } if(vec.size()==0||vec.size()==1) { printf("Ambiguous"); continue; } int cnt=0; ans=0; dfs(0); if(ans==0) printf("Impossible\n"); else if(ans>1) printf("Ambiguous\n"); else { for(int i=0;i<n;i++) { if(i==vec[cnt]&&cnt<vec.size()) printf("%c",s_ans[cnt]+'a'),cnt++; else printf("%c",s1[i]); } printf("\n"); } } return 0; }
