Cod sursa(job #40352)

Utilizator pocaituDavid si Goliat pocaitu Data 27 martie 2007 13:07:04
Problema ADN Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<fstream.h>
#include<string.h>
#include<stdlib.h>
#define nmax 30004
#define tmax 100000
int n,m[19][19],adev[nmax];
char s[19][nmax];
long lung,d,viz[19],i,j,k,n1,n2;
void rezolva();
void afiseaza(int d[100]);

int main()
{ifstream f("adn.in");
 f>>n;
 for(i=1;i<=n;i++)
  f>>s[i];
// daca unul contine pe celalalt
memset(viz,0,sizeof(viz));
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  if(i!=j&&strstr(s[i],s[j]))
	viz[j]=1;
for(i=1,d=0;i<=n;i++)
 if(!viz[i])
   {memcpy(s[++d],s[i],sizeof(s[i]));
	lung+=strlen(s[i]);
	}
n=d;

for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  if(j!=i)
   {memset(adev,1,sizeof(adev));
	for(k=0,n1=strlen(s[i]),n2=strlen(s[j]);k<n1;k++)
	  for(d=0;d<k;d++)
		if(s[j][d]!=s[i][n1-(k-d)])
		  {adev[k]=0;break;}
	for(k=n1-1;k>=0;k--)
	  if(adev[k])
		{m[i][j]=k;break;}

   }
rezolva();

return 0;
}

void rezolva()
{//randomize();
 int j,x,viz[19],s[19],d[19];
 long l,i,min=1000000;

 for(k=1;k<=tmax;k++)
  {memset(viz,0,sizeof(viz));
   for(j=1;j<=n;j++)
	{
	 //do{
	   x=rand()%n+1;
	  // }
		while(viz[x]&&x) x--;
	 if(!x) {x=n; while(!viz[x]) x--;}
	 viz[x]=1;
	 s[j]=x;
	 }
   for(j=1,l=lung;j<n;j++)
	 l-=m[s[j]][s[j+1]];
   if(l<min)
	{min=l;memcpy(d,s,sizeof(s));}
   }
afiseaza(d);

}



void afiseaza(int d[100])
{int i,j;
ofstream g("adn.out");
 for(i=1;i<n;i++)
  for(j=0;j<=strlen(s[d[i]])-m[d[i]][d[i+1]]-1;j++)
   g<<s[d[i]][j];
 g<<s[d[i]];
 g.close();
 }