Cod sursa(job #115)

Utilizator alextheroTandrau Alexandru alexthero Data 5 decembrie 2006 13:18:23
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <stdio.h>
#include <string.h>

#define nmax 20
#define lmax 30005
#define infinite 1000000
#define confmax 270000


long comps=0,comps1=0,n,cost,mmax,care,cost_max,cmax,cate[nmax],d[nmax][nmax],bagat[nmax],p[lmax],rez[nmax],aux[nmax],place[nmax][nmax],powe[nmax+1];
long cc[nmax][confmax],pd[nmax][confmax];
long prev[nmax][confmax];
char a[nmax][lmax];

void citire() {
     scanf("%d\n",&n);    
     char ch;
     for(long i=1;i<=n;i++) {
             cate[i]=1;
             scanf("%s\n",&a[i]);
             cate[i]=strlen(a[i]);
             for(long j=cate[i]+1;j>=1;j--) a[i][j]=a[i][j-1];
     }
}

void kmp_calculeaza(long x) {
     long n=cate[x];
     long k=0;
     p[1]=0;
     for(int i=2;i<=n;i++) {
         while ((k>0) && (a[x][k+1]!=a[x][i])) k=p[k];
         if(a[x][k+1]==a[x][i]) k++;
         p[i]=k;
     }    
}

long kmp_potrivire(long x,long y) {
	 int q=0;
     int m=cate[y];
     int n=cate[x];
     for(long i=1;i<=m;i++) {
             while((q>0) && (a[x][q+1]!=a[y][i])) q=p[q];
             if(a[x][q+1]==a[y][i]) {
                              q++;
                              if(q==n) return q;
                              }             
             }  
     if(q==n) return 0;  
     return q;
}

long kmp(long x,long y) {
    kmp_calculeaza(x);
    return kmp_potrivire(x,y);
}

int nr1(long x) {
    int cate=0;
	while(x!=0) {
			cate+=x %2;
			x/=2;
    }   
    return cate;
}

int main() {
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);
    
	citire();
	long i,j;
	for(i=1;i<=n;i++) bagat[i]=1;
	for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
                    if ((i!=j) && (bagat[i]) && (bagat[j])) {
                             long x=kmp(i,j);
                             if(x==cate[i]) bagat[i]=0;
                             d[j][i]=x;
                             }
    powe[0]=1;
	for(i=1;i<=nmax;i++) powe[i]=powe[i-1]*2;


	long conf;
	for(conf=1;conf<powe[n];conf++) {
			 long nr_1=nr1(conf);
             cc[nr_1][++cc[nr_1][0]]=conf;
    }
    
	memset(pd,-1,sizeof(pd));

	for(i=1;i<=n;i++) pd[i][powe[i-1]]=0;

	long k;

	long maxi=0,maxx,maxy;
	int max1=0;

	for(k=1;k<n;k++)
	  for(j=1;j<=cc[k][0];j++) {
		long copy=cc[k][j];
		for(int x1=1;x1<=n;x1++) {
			if(copy%2==1) {
			  if ((pd[x1][cc[k][j]]!=-1) && (bagat[x1])) {
				 long copy1=cc[k][j];
				 for(int x2=1;x2<=n;x2++) {
					 if(copy1%2==0) {
						long newconf=cc[k][j]+powe[x2-1];
						if ((pd[x2][newconf]<pd[x1][cc[k][j]]+d[x1][x2]) && (bagat[x2])) {
						   pd[x2][newconf]=pd[x1][cc[k][j]]+d[x1][x2];
						   prev[x2][newconf]=x1*1000000+cc[k][j];
                        }
						if ((pd[x2][newconf]>=maxi) && (bagat[x2])) {
							maxi=pd[x2][newconf];
							maxx=x2;
							maxy=newconf;
						}
					 }
					 copy1/=2;
				 }
			   }
			 }
			 copy/=2;
		}
	}
	
	int bb[nmax];
	bb[0]=0;

	while(prev[maxx][maxy]!=0) {
                               bb[++bb[0]]=maxx;
                               int maux=maxx;
                               maxx=prev[maxx][maxy]/1000000;
                               maxy=prev[maux][maxy]%1000000;
    }
    bb[++bb[0]]=maxx;
    
    bb[bb[0]+1]=0;    
    for(long i=bb[0];i>=1;i--) {
            long n2=bb[i];
            long n1=bb[i+1];
            for(long j=1+d[n1][n2];j<=cate[n2];j++) printf("%c",a[n2][j]);
    }

    return 0;
}