Cod sursa(job #652912)

Utilizator yonnssyonns yonns yonnss Data 26 decembrie 2011 19:00:54
Problema ADN Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.53 kb
#include <stdio.h>
#include <string.h>
#include <time.h>
//#include <conio.h>
struct Secv
{
    char sir[30001];
    int l;
} secvente[20];
int n;
int m[20][20];
int min=2000000000;

int vmin[20];
int comun(int primu, int aldoilea){
    int j,i;
    int k;
    int lp,ld;
    int comune=0;
    int max=0;
    lp=secvente[primu].l;
    ld=secvente[aldoilea].l;

    for(i=lp;i>=0;i--) {
        comune=0;
        j=0;
        k=i;
        while(j<ld && k<lp && j<lp-i){
            if(secvente[primu].sir[k]==secvente[aldoilea].sir[j]) {
            comune++;

            }
            else break;
            k++;
            j++;


        }
        if(comune>max && (k==lp ||j==ld)) max=comune;
        if(comune==ld) break;


    }
    return max;
}

void determinacomune(){
    int i,j;
    for(i=0;i<n;i++) for(j=0;j<n;j++) if(i!=j){
    m[i][j]=comun(i,j);


    }



}

void citeste()
{
    FILE *f=fopen("adn.in","r");
    fscanf(f,"%d",&n);
    int i;
    for(i=0; i<n; i++) {
        fscanf(f,"%s",secvente[i].sir);
        secvente[i].l=strlen(secvente[i].sir);
    }
    fclose(f);
}

void sterge(){
int x,y;
int l;
int b=0;
int nn=n;
int i,j;
for(x=0;x<n;x++) {
    l=secvente[x].l;
    b=0;
    for(y=0;y<n;y++) if(m[y][x]==l) { b=1; break; }
    if(b){
    for(i=x+1;i<n;i++) secvente[i-1]=secvente[i];
    for(y=x+1;y<n;y++) for(i=0;i<n;i++) m[y-1][i]=m[y][i];
    for(y=x+1;y<n;y++) for(i=0;i<n;i++) m[i][y-1]=m[i][y];
    nn--;
    }
}
n=nn;
}
int verificaunicitate(int vect[20],int i){
if(vect[i]!=-1) return 0;
return 1;

}
void determina(int linie, int start,int l,int indice,int vect[20],int ordine){
    int ltemp;
 // if(ordine==n)  for(int j=0;j<n;j++) printf("%d ",vect[j]);
    //printf("%s  %d\n",s,l);
   // getche();
 // printf("  %d\n",l);

    if(ordine==n)
    if(l<min) {  for(int c=0;c<n;c++) vmin[c]=vect[c]; min=l; return ; }
    else return ;


    int i;

    for(i=0;i<n;i++)  {
       if(vect[i]==-1) {
       vect[i]=ordine;
    //   printf("pune peste %s %s la %d\n",s,secvente[i].sir,m[linie][i]);
    //   strcat(s,secvente[i].sir+m[linie][i]);
       ltemp=l+secvente[i].l-m[linie][i];
       if(ltemp<=min && ordine <n)
       determina(i,start,ltemp,ltemp,vect,ordine+1);
       vect[i]=-1;
//       s[indice]='\0';
       }

    }


}
int main()
{
    citeste();
     //   for(int i=0;i<n;i++) printf("%s\n",secvente[i].sir);
    int x,y;

    determinacomune();
    sterge();

   // determinacomune();
  //   for(y=0;y<n;y++) {
  //  for(x=0;x<n;x++) printf("%d ",m[y][x]);
  //  printf("\n");

  //  }
  //  for(int i=0;i<n;i++) printf("%s\n",secvente[i].sir);
    int v[20];
    for(int i=0;i<20;i++) v[i]=-1;
    //char sir[540000]="";
    char mins[540000]="\0";
    //strcpy(sir,secvente[0].sir);
    int i;

    for(i=0;i<n;i++) {
        v[i]=0;
        //strcpy(sir,secvente[i].sir);
        determina(i,0,secvente[i].l,secvente[i].l,v,1);
        v[i]=-1;


    }


  //  for(y=0;y<n;y++) {
  //  for(x=0;x<n;x++) printf("%d ",m[y][x]);
  //  printf("\n");

 //   }
 int contor=0;
 int ant,salt=0;
 mins[0]='\0';
 int b=1;
 while(contor<n){
    for(i=0;i<n;i++) if(vmin[i]==contor) {
        if(contor)
        strcat(mins,secvente[i].sir+m[ant][i]);
        else strcpy(mins,secvente[i].sir);
        break;
        }
        contor++;
        ant=i;

 }
 FILE *out=fopen("adn.out","w");
//printf("%d",min);
    fprintf(out,"%s\n",mins);
    fclose(out);
    return 0;
}