Pagini recente » Cod sursa (job #371691) | Cod sursa (job #879418) | Cod sursa (job #1299106) | Cod sursa (job #2157815) | Cod sursa (job #2136575)
/*
#include <fstream>
#include <queue>
using namespace std;
#define Max 1002
int a[Max][Max], d[Max][Max];
int x1,y1,x2,y2,R,C;
queue<int> qx,qy;
int Lee(int k)
{
int i,j,p;
while (!qx.empty()) qx.pop(); while (!qy.empty()) qy.pop();
for (i=1;i<=R;i++)
for (j=1;j<=C;j++)
if(a[i][j]>0) a[i][j]=0;
qx.push(x1); qy.push(y1); a[x1][y1]=1;
while (!qx.empty()) {
i=qx.front(); qx.pop(); j=qy.front(); qy.pop();
p=a[i][j];
if (a[i][j+1]==0 && d[i][j+1]>=k) {a[i][j+1]=p+1; qx.push(i); qy.push(j+1);}
if (a[i-1][j]==0 && d[i-1][j]>=k) {a[i-1][j]=p+1; qx.push(i-1); qy.push(j);}
if (a[i][j-1]==0 && d[i][j-1]>=k) {a[i][j-1]=p+1; qx.push(i); qy.push(j-1);}
if (a[i+1][j]==0 && d[i+1][j]>=k) {a[i+1][j]=p+1; qx.push(i+1); qy.push(j);}
if (a[x2][y2]>0) return 1;
}
return 0;
}
int main()
{
int i,j,p,k=0,mx=0;
char s[Max+1];
ifstream f1("barbar.in"); ofstream f2("barbar.out");
f1>>R>>C;
for (i=0;i<=R+1;i++) a[i][0]=a[i][C+1]=d[i][0]=d[i][C+1]=-1;
for (j=0;j<=C+1;j++) a[0][j]=a[R+1][j]=d[0][j]=d[R+1][j]=-1;
for (i=1;i<=R;i++) {
f1>>s;
for (j=0;j<C;j++) {
if (s[j]=='*') {a[i][j+1]=-1; d[i][j+1]=-1;}
if (s[j]=='I') {x1=i; y1=j+1;}
if (s[j]=='O') {x2=i; y2=j+1;}
if (s[j]=='D') {d[i][j+1]=1; qx.push(i); qy.push(j+1);}
}
}
while (!qx.empty()) {
i=qx.front(); qx.pop(); j=qy.front(); qy.pop();
p=d[i][j];
if (d[i][j+1]==0) {d[i][j+1]=p+1; qx.push(i); qy.push(j+1);}
if (d[i-1][j]==0){d[i-1][j]=p+1; qx.push(i-1); qy.push(j);}
if (d[i][j-1]==0) {d[i][j-1]=p+1; qx.push(i); qy.push(j-1);}
if (d[i+1][j]==0) {d[i+1][j]=p+1; qx.push(i+1); qy.push(j);}
}
mx=d[x1][y1];
while (k==0 && mx>0) {
k=Lee(mx);
mx--;
}
if (k) f2 << mx;
else f2 << -1;
return 0;
}
*/
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
#define Max 32000
int main()
{
ifstream fin("adn.in"); ofstream fout("adn.out");
int i,j,n,k,s,mx=0,p[20],pmax[20],D[20][20],L[20];
char cuv[20][Max],c[Max];
fin>>n;
for (i=0;i<n;i++)
{fin>>cuv[i]; L[i]=strlen(cuv[i]);}
for (i=0;i<n;i++) // ordonare dupa lungine
for (j=i+1;j<n;j++)
if (L[i]<L[j])
{swap(cuv[i],cuv[j]); swap(L[i],L[j]);}
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
if (strstr(cuv[i],cuv[j])) L[j]=0;
for (i=0;i<n;i++) // eliminare cuvinte continute in alte cuvinte
if (L[i]==0)
{swap(L[i],L[n-1]); n--;}
for (i=0;i<n;i++) { // calcul cat "intra" un cuvant in alt cuvant
strcpy(c,cuv[i]);
for (j=0;j<n;j++) {
k=min(L[i],L[j]);
while (k>0 && strncmp(c+L[i]-k,cuv[j],k)!=0)k--;
D[i][j]=k;
}
}
for (i=0;i<n;i++) p[i]=i;
do {
s=0;
for (i=1;i<n;i++) s+=D[p[i-1]][p[i]];
if (s>mx)
{mx=s; for(j=0;j<n;j++) pmax[j]=p[j];}
} while (next_permutation(p,p+n));
fout<<cuv[pmax[0]];
for(i=1;i<n;i++) {strcpy(c,cuv[pmax[i]]);fout<<c+D[pmax[i-1]][pmax[i]];}
return 0;
}