Cod sursa(job #1009674)

Utilizator ScoobyDoo38Nita Adrian Valentin ScoobyDoo38 Data 13 octombrie 2013 17:11:42
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
class Problem
{
private:
    int n;
    vector< string > sec;
 
    unsigned bestsize;
    string best;
 
public:
    Problem( string input )
    {
        ifstream in( input );
 
        in >> n;
 
        sec.resize( n );
        for ( auto& i: sec )
        {
            in >> i;
        }
 
        in.close();
 
        bestsize = string::npos;
 
        solve();
    }
 
private:
    void solve()
    {
        vector< string > buff;
        vector< string > hold;
 
        sort( sec.begin(), sec.end() );
 
        do
        {
            hold = sec;
 
            while ( hold.size() > 1 )
            {
                int hsz = hold.size();
 
                buff.resize( ( hsz + 1 ) / 2 );
 
                for ( int i = 0, j = 0; i + 1 < hsz; i += 2, j++ )
                {
                    char ch = hold[ i + 1 ].front();
                    int sz = hold[ i + 1 ].size();
                    int delta = 0;
 
                    for ( int j = 0, h = hold[ i ].size(); j < h; j++ )
                    {
                        if ( hold[ i ][ j ] == ch )
                        {
                            int d = 1;
                            while ( j + d < h && d < sz && hold[ i ][ j + d ] == hold[ i + 1 ][ d ] )
                            {
                                d++;
                            }
 
                            if ( j + d == h )
                            {
                                delta = d;
                                break;
                            }
                        }
                    }
 
                    buff[ j ] = hold[ i ].substr( 0, hold[ i ].size() - delta ) + hold[ i + 1 ];
                }
 
                if ( hsz % 2 == 1 )
                {
                    buff[ hsz / 2 ] = hold.back();
                }
 
                hold = buff;
            }
 
            if ( hold.front().size() < bestsize )
            {
                best = hold.front();
                bestsize = hold.front().size();
            }
 
        } while ( next_permutation( sec.begin(), sec.end() ) );
    }
 
public:
    void showResult( string output )
    {
        ofstream out( output );
 
        out << best;
 
        out.close();
    }
};
 
int main()
{
    Problem* p = new Problem( "adn.in" );
    p->showResult( "adn.out" );
     
    return 0;
}