Cod sursa(job #1490253)

Utilizator ZeratulVeress Szilard Zeratul Data 23 septembrie 2015 00:28:50
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.17 kb
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>

using namespace std;


string s[18];
bool b[18];
int t[18][18];
int best=0;
int best_sorrend[18];
int n;

void tovabblep (int most, int sum, int sorrend[], int counter)
{
    bool goon=false;

    for (int i=0;i<n;i++)
    {
        if (b[i] and i!=most)
        {
            goon=true;
        }
    }

   if(goon)
   {
        for (int i=0;i<n;i++)
        {
            if (i!=most and b[i] and t[most][i]>0)
            {
                sorrend[counter]=most;
                b[most]=false;
                tovabblep(i,sum+t[most][i], sorrend, counter+1);
                b[most]=true;
            }
        }
   }
   else
   {
        if (sum>best)
        {
            best=sum;
            for (int i=0;i<n;i++)
            {
                best_sorrend[i]=sorrend[i];
            }
            best_sorrend[counter]=most;
        }
   }
}

int main()
{
    ifstream be("ADN.in");
    ofstream ki("ADN.out");
    be>>n;
    int biggest_nr;
    int sorrend[18];

    getline(be,s[0]);
    for (int i=0;i<n;i++)
    {
        b[i]=true;
        sorrend[i]=-1;
        getline(be,s[i]);
    }

    best_sorrend[n]=-1;

    for (int i=0;i<n;i++)
    {
        for (int pp=0;pp<n;pp++)
        {
            biggest_nr=pp;
            if (s[i].size()<=s[biggest_nr].size() and i!=biggest_nr and b[biggest_nr]==true)
            {
                for (int j=0;j<s[biggest_nr].size();j++)
                {
                    if (s[i].size()>s[biggest_nr].size()-j)
                    {
                        break;
                    }
                    if (s[biggest_nr][j]==s[i][0])
                    {
                        bool reszhalmaz=true;

                        for (int p=0;p<s[i].size();p++)
                        {
                            if (s[i][p]!=s[biggest_nr][j+p])
                            {
                                reszhalmaz=false;
                                break;
                            }
                        }
                        if (reszhalmaz)
                        {
                            b[i]=false;
                        }
                    }
                }
            }
        }
    }

    /*for (int i=0;i<n;i++)
    {
        cout<<b[i];
    }*/

    for (int i=0;i<n;i++)
    {
        t[i][i]=-1;
    }

    for (int i=0;i<n;i++)
    {
        if (b[i])
        {
            for (int j=0;j<n;j++)
            {
                if (i!=j and b[j])
                {
                    bool talal;
                    int q=0;
                    while(q<s[i].size() and q<s[j].size())
                    {
                        talal=true;
                        for (int p=0;p<=q;p++)
                        {
                            if (s[i][s[i].size()-1-q+p]!=s[j][p])
                            {
                                talal=false;
                            }
                        }
                        if (talal)
                        {
                            t[i][j]=q+1;
                        }
                        q++;
                    }
                }
            }
        }
    }

    /*cout<<endl;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (t[i][j]==-1)
            {
                cout<<setw(3)<<" ";
            }
            else
            cout<<setw(3)<<t[i][j]<<" ";
        }
        cout<<endl;
    }*/

    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (i!=j and b[i] and b[j] and t[i][j]>0)
            {
                sorrend[0]=i;
                b[i]=false;
                tovabblep( j, t[i][j], sorrend, 1);
                b[i]=true;
            }
        }
    }

    int i=1;
    ki<<s[best_sorrend[0]];
    while (best_sorrend[i]!=-1)
    {
        for (int j=t[best_sorrend[i-1]][best_sorrend[i]];j<s[best_sorrend[i]].size();j++)
        {
            ki<<s[best_sorrend[i]][j];
        }
        i++;
    }

    return 0;
}