Cod sursa(job #2136575)

Utilizator anamaria_nosaAnamaria Nosa anamaria_nosa Data 19 februarie 2018 23:34:31
Problema ADN Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.31 kb
/*
#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;
}