Cod sursa(job #1490387)
Utilizator | 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;
}