Cod sursa(job #1009446)

Utilizator ScoobyDoo38Nita Adrian Valentin ScoobyDoo38 Data 13 octombrie 2013 10:49:16
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Problem
{
private:
	int n;
	vector< string > sec;

	int 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;
}