Cod sursa(job #1490387)

Utilizator ZeratulVeress Szilard Zeratul Data 23 septembrie 2015 13:25:15
Problema ADN Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.67 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)
   {
            //cout<<endl<<"tovabblep: "<<counter;
            int top3_value[3]= {0,0,0};
            int top3[3];
            for (int j=0;j<n;j++)
            {
                if (b[j] and t[most][j]>=top3_value[2])
                {
                    if (t[most][j]>=top3_value[1])
                    {
                        if (t[most][j]>=top3_value[0])
                        {
                            top3_value[2]=top3_value[1];
                            top3_value[1]=top3_value[0];
                            top3_value[0]=t[most][j];
                            top3[2]=top3[1];
                            top3[1]=top3[0];
                            top3[0]=j;
                        }
                        else
                        {
                            top3_value[2]=top3_value[1];
                            top3_value[1]=t[most][j];
                            top3[2]=top3[1];
                            top3[1]=j;
                        }
                    }
                    else
                    {
                        top3_value[2]=t[most][j];
                        top3[2]=j;
                    }
                }
            }

            //cout<<endl<<"Found top3";
            for (int i2=0;i2<3;i2++)
            {
                if (top3_value[i2]==0)
                {
                    break;
                }
                //cout<<endl<<top3[i2]<<"  "<<top3_value[i2];
            }

        for (int j=0;j<3;j++)
        {
                if (top3_value[j]==0)
                {
                    break;
                }
                sorrend[counter]=most;
                b[most]=false;
                tovabblep(top3[j],sum+top3_value[j], 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++;
                    }
                }
            }
        }
    }

    for (int i=0;i<n;i++)
    {
        if (b[i])
        {
            int top3_value[3]= {0,0,0};
            int top3[3];
            for (int j=0;j<n;j++)
            {
                if (b[j] and t[i][j]>=top3_value[2])
                {
                    if (t[i][j]>=top3_value[1])
                    {
                        if (t[i][j]>=top3_value[0])
                        {
                            top3_value[2]=top3_value[1];
                            top3_value[1]=top3_value[0];
                            top3_value[0]=t[i][j];
                            top3[2]=top3[1];
                            top3[1]=top3[0];
                            top3[0]=j;
                        }
                        else
                        {
                            top3_value[2]=top3_value[1];
                            top3_value[1]=t[i][j];
                            top3[2]=top3[1];
                            top3[1]=j;
                        }
                    }
                    else
                    {
                        top3_value[2]=t[i][j];
                        top3[2]=j;
                    }
                }
            }

            /*for (int i2=0;i2<3;i2++)
            {
                cout<<endl<<top3[i2]<<"  "<<top3_value[i2];
            }*/

            for (int j=0;j<3;j++)
            {
                sorrend[0]=i;
                b[i]=false;
                //cout<<endl<<j;
                tovabblep( top3[j], top3_value[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;
}