Cod sursa(job #751464)

Utilizator geniucosOncescu Costin geniucos Data 26 mai 2012 10:21:43
Problema ADN Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<cstdio>
#include<cstring>
using namespace std;
int nr,nr1,mini,n,i,j,k,p,l[20],c[20][20],ap[20],d[20][20],x[20],s[20];
char a[20][30002],sm[600002];
int min(int a,int b)
{
	if(a<b) return a;
	return b;
}
int valid(int k)
{
	if(s[k]>mini) return 0;
	if(ap[x[k]]!=1) return 0;
	return 1;
}
void back()
{
	k=1;
	x[k]=0;
	ap[0]=1;
	s[0]=0;
	while(k>0)
	{
		while(x[k]<n&&k<=n-nr1)
		{
			ap[x[k]]--;
			x[k]++;
			ap[x[k]]++;
			s[k]=s[k-1]+l[x[k]]-c[x[k-1]][x[k]];
			if(valid(k))
			{
				if(k==n-nr1&&s[k]<mini)
				{
					mini=s[k];
					nr=0;
					for(i=1;i<=n-nr1;i++)
						for(j=d[x[i-1]][x[i]];j<=l[x[i]];j++)
						{
							nr++;
							sm[nr]=a[x[i]][j];
						}
				}
				else
				if(k<n-nr1)
				{
					k++;
					x[k]=0;
					ap[0]++;
				}
			}
		}
		ap[x[k]]--;
		k--;
	}
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
	gets(a[i]+1);
	l[i]=strlen(a[i]+1);
}
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		d[i][j]=1;
for(i=1;i<=n;i++)
{
	for(j=1;j<=n;j++)
		if(i!=j)
		{
			if(l[i]==l[j]&&strcmp(a[i]+1,a[j]+1)==0) break;
			else
			if(l[i]<l[j])
			{
				for(p=1;p<=l[j]-l[i]+1;p++)
				{
					for(k=p;k<=p+l[i]-1;k++)
						if(a[j][k]!=a[i][k-p+1]) break;
					if(k>p+l[i]-1) break;
				}
				if(p<=l[j]-l[i]+1) break;
			}
		}
	if(j<=n)
	{
		ap[i]=1;
		nr1++;
	}
}
for(j=1;j<=n;j++)
	for(i=1;i<=n;i++)
		if(ap[i]==0&&ap[j]==0&&i!=j)
		{
			for(p=1;p<=l[j];p++)
			{
				for(k=p;k<=min(l[j],p+l[i]-1);k++)
					if(a[j][k]!=a[i][k-p+1]) break;
				if(k>min(l[j],k+l[i]-1)) break;
			}
			c[j][i]=l[j]-p+1;
			d[j][i]=c[j][i]+1;
		}
for(i=1;i<=n;i++)
{
	c[0][i]=0;
	d[0][i]=1;
}
mini=1000000000;
back();
//printf("%s\n",sm+1);
for(i=1;i<=mini;i++)
	printf("%c",sm[i]);
return 0;
}