Pagini recente » Cod sursa (job #3256077) | Cod sursa (job #3205669) | Cod sursa (job #648228) | Cod sursa (job #1193355) | Cod sursa (job #2243448)
// https://infoarena.ro/problema/adn
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
//#ifndef DEBUG
//#define DEBUG
//#endif
std::ifstream in("adn.in");
std::ofstream out("adn.out");
std::vector<std::string> adn;
std::string::size_type* adnmat;
unsigned int n;
int main()
{
in >> n;
std::string::size_type maxstr = 0;
{
std::string temp;
adn.reserve(n);
for(unsigned int i = 0; i < n; i++)
{
in >> temp;
maxstr += temp.size();
adn.push_back(temp);
}
temp.clear();
}
adnmat = (std::string::size_type*)calloc(n * n, sizeof(*adnmat));
for(unsigned int i = 0; i < n - 1; i++)
{
for(unsigned int j = i + 1; j < n; j++)
{
if(adn[i].find(adn[j]) != std::string::npos)
adnmat[i * n + j] = std::string::npos;
else
for(std::string::size_type d = 1; d <= adn[i].size(); d++)
if(adn[j].find(adn[i].substr(d)) == 0)
{
adnmat[i * n + j] = adn[i].size() - d;
break;
}
if(adn[j].find(adn[i]) != std::string::npos)
adnmat[j * n + i] = std::string::npos;
else
for(std::string::size_type d = 1; d <= adn[j].size(); d++)
if(adn[i].find(adn[j].substr(d)) == 0)
{
adnmat[j * n + i] = adn[j].size() - d;
break;
}
}
}
#ifdef DEBUG
for(unsigned int i = 0; i < n; i++)
{
for(unsigned int j = 0; j < n; j++)
if(adnmat[i * n + j] != std::string::npos)
out << std::setw(5) << adnmat[i * n + j];
else
out << " npos";
out << std::endl;
}
#endif // DEBUG
unsigned int over;
unsigned int mover = 0;
std::vector<unsigned int> ovec;
std::vector<unsigned int> movec;
ovec.reserve(n);
movec.reserve(n);
for(unsigned int i = 0; i < n; i++)
ovec.push_back(i);
do
{
over = 0;
for(unsigned int i = 0; i < n - 1; i++)
if(adnmat[ovec[i] * n + ovec[i + 1]] != std::string::npos)
over += adnmat[ovec[i] * n + ovec[i + 1]];
else
over += adn[ovec[i]].size();
if(over >= mover)
{
mover = over;
movec = ovec;
}
}
while(std::next_permutation(ovec.begin(), ovec.end()));
#ifdef DEBUG
for(unsigned int i = 0; i < n; i++)
out << movec[i] + 1 << ' ';
out << std::endl;
#endif // DEBUG
std::string fin;
fin.reserve(maxstr);
fin += adn[movec[0]];
for(unsigned int i = 1; i < n; i++)
if(adnmat[movec[i - 1] * n + movec[i]] != std::string::npos)
fin += adn[movec[i]].substr(adnmat[movec[i - 1] * n + movec[i]]);
out << fin << std::endl;
#ifdef DEBUG
out << "AGATAGATGATAACCGCGCAGTGATGAGATGGGGATATAAAAACTTTTTT " << (fin == (std::string)"AGATAGATGATAACCGCGCAGTGATGAGATGGGGATATAAAAACTTTTTT") << std::endl;
#endif
in.close();
out.close();
return 0;
}