Cod sursa(job #1058220)

Utilizator NaniteNanite Nanite Data 15 decembrie 2013 11:46:30
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <fstream>
#include <iostream>

using namespace std;

const unsigned int maxl = 30000,
                    maxn = 18;
int N;
string s[maxn],
        stringBuffer,
        S = "";
int st[maxn];




inline void read() {
    ifstream fileInStream("adn.in");
    fileInStream >> N;
    for(int i = 0; i < N; i++) {
        fileInStream >> s[i];
    }
}

inline void write() {
    ofstream fileOutStream("adn.out");
    fileOutStream << S;
}

bool equals(string &b, unsigned int pos1, unsigned short stringIndex, unsigned int pos2, unsigned int length) {
    unsigned int i = pos1;
    while(i - pos1 < length) {
        if(b[i++] != s[st[stringIndex]][pos2++]) {
            return false;
        }
    }

    return true;
}

string process() {
    unsigned int x;
    string buffer = "";
    for(int i = 0; i < N; ++i) {
        for(buffer.length() < s[st[i]].length() ? x = buffer.length() : x = s[st[i]].length(); x >= 0; --x) {
            if(equals(buffer, buffer.length()-x, i, 0, x)) {
                buffer += s[st[i]].substr(x, s[st[i]].length()-x);
                break;
            }
        }
    }

    return buffer;
}


/*void permute(unsigned int it) {
    if(it == N) {
        stringBuffer = process();
        if(S == "" || stringBuffer.length() < S.length()) {
            S = stringBuffer;
        }
    } else {
        for(unsigned int i = 0; i < N; ++i) {
            swap(s[i], s[it]);
            permute(it+1);
            swap(s[i], s[it]);
        }
    }
}*/

void init(int k) {
    st[k] = -1;
}

bool scc(int k) {
    if(st[k] < N-1) {
        st[k]++;
        return true;
    }
    return false;
}

bool val(int k) {
    for(int i = 0; i < k; i++) {
        if(st[i] == st[k]) {
            return false;
        }
    }
    return true;
}

bool sol(int k) {
    return k == N-1;
}

void backtracking() {
    int k = 0;
    bool e, v;

    init(k);
    while(k > -1) {
        do {
            e = scc(k);
            if(e) v = val(k);
        }while(e && !v);

        if(e) {
            if(sol(k)) {
                stringBuffer = process();
                if(S == "" || stringBuffer.length() < S.length()) {
                    S = stringBuffer;
                }
            } else {
                k++;
                init(k);
            }
        } else {
            k--;
        }
    }
}

int main() {
    read();
    backtracking();
    //permute(0);
    write();



    return 0;
}