Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


History
2017-05-27 12:25:20
Task:Median string
Sender:Game of Nolife
Submission time:2017-05-27 12:25:20
Status:READY
Result:ACCEPTED

Show test data

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

struct fro{
	int a,b,c;
	char ch;
};

int dp[55][55][55];
fro dpf[55][55][55];

void go(int a, int b, int c, int v, fro f){
	if (v<dp[a][b][c]){
		dp[a][b][c]=v;
		dpf[a][b][c]=f;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string a,b,c;
	cin>>a>>b>>c;
	int as=a.size();
	int bs=b.size();
	int cs=c.size();
	for (int i=0;i<=as;i++){
		for (int ii=0;ii<=bs;ii++){
			for (int iii=0;iii<=cs;iii++){
				dp[i][ii][iii]=1e9;
			}
		}
	}
	dp[0][0][0]=0;
	for (int i=0;i<=as;i++){
		for (int ii=0;ii<=bs;ii++){
			for (int iii=0;iii<=cs;iii++){
				int tc=dp[i][ii][iii];
				for (int j=0;j<8;j++){
					int ni=i;
					int nii=ii;
					int niii=iii;
					if ((j&1)>0&&i==as) continue;
					else if (j&1) ni=i+1;
					if ((j&2)>0&&ii==bs) continue;
					else if (j&2) nii=ii+1;
					if ((j&4)>0&&iii==cs) continue;
					else if (j&4) niii=iii+1;
					for (char ch='A';ch<='Z';ch++){
						int co=0;
						if ((j&1)>0){
							if (a[i]!=ch) co++;
						}
						else co++;
						if ((j&2)>0){
							if (b[ii]!=ch) co++;
						}
						else co++;
						if ((j&4)>0){
							if (c[iii]!=ch) co++;
						}
						else co++;
						go(ni, nii, niii, tc+co, {i, ii, iii, ch});
					}
					go(ni, nii, niii, tc+__builtin_popcount(j), {i, ii, iii, ' '});
				}
			}
		}
	}
	int be=1e9;
	int bea=0;
	int beb=0;
	int bec=0;
	for (int i=0;i<=as;i++){
		for (int ii=0;ii<=bs;ii++){
			for (int iii=0;iii<=cs;iii++){
				int ac=as-i+bs-ii+cs-iii;
				if (dp[i][ii][iii]+ac<be){
					be=dp[i][ii][iii]+ac;
					bea=i;
					beb=ii;
					bec=iii;
				}
			}
		}
	}
	string ans;
	while (bea>0||beb>0||bec>0){
// 		cout<<bea<<" "<<beb<<" "<<bec<<endl;
		if (dpf[bea][beb][bec].ch!=' ') ans+=dpf[bea][beb][bec].ch;
		int na=dpf[bea][beb][bec].a;
		int nb=dpf[bea][beb][bec].b;
		int nc=dpf[bea][beb][bec].c;
		bea=na;
		beb=nb;
		bec=nc;
	}
	reverse(ans.begin(), ans.end());
	cout<<ans<<endl;
}