Cod sursa(job #2158375)

Utilizator andr3i_kaabAndrei Ciineanu andr3i_kaab Data 10 martie 2018 12:25:38
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
//#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("adn.in");
ofstream cout("adn.out");

const int N=32;
int a[N][N], n, tot, viz[N], ord[N], mx, op;
string s[N];

int main()
{
    int i, j, ok=0, s1;
    f>>n;
    for (i=1; i<=n; i++)
       { f>>s[i]; tot+=s[i].length(); viz[i]=i; }

    for (i=1; i<=n; i++)
      for (j=1; j<=n; j++)
    if (i!=j && s[i].find(s[j])!=string::npos) { viz[j]=0; op++; }

    for (i=1; i<=n; i++)
        if (viz[i]==0)
    {
        for (j=i; j<n; j++) { s[j]=s[j+1];}
    }
    n-=op;
// cout<<n<<"\n";

 //for (i=1;i<=n;i++) {cout<<s[i]<<" "; viz[i]=i;} // cout<<viz[i]; cout<<"\n";
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
    {
        int k, p; string ux1, ux2;

        p=min(s[i].length(),s[j].length());



        for ( k=1; k<=p ;k++) {

          ux1=s[j].substr(0,k);
          ux2=s[i].substr(s[i].length()-k,k);
  //cout<<ux1<<"-"<<ux2<<"   ";
          if(ux1==ux2)
            a[i][j]=k;
        }
    }
   /* for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++) cout<<a[i][j]<<" ";
        cout<<"\n";
    }*/

    mx=999999;
    while (next_permutation(viz+1, viz+n+1))
    {
        s1=s[viz[1]].length();
        for (i=2; i<=n; i++)
            s1+=s[viz[i]].length()-a[viz[i-1]][viz[i]];
        if (s1<mx)
        {
            for (i=1; i<=n; i++) ord[i]=viz[i];
            mx=s1;
        }
    }

    //cout<<mx<<"\n";
   // for (i=1;i<=n;i++) cout<<ord[i]<<" "; cout<<"\n";
   // cout<<s[ord[1]];
    for (i=2; i<=n; i++)
        cout<<s[ord[i]].substr(a[ord[i-1]][ord[i]], s[ord[i]].length()-a[ord[i-1]][ord[i]]);
    return 0;
}