Cod sursa(job #2030976)

Utilizator alexpetrescuPetrescu Alexandru alexpetrescu Data 2 octombrie 2017 16:15:59
Problema Seif Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <algorithm>

#define MAXN 1000

short int dp[MAXN + 1][MAXN + 1];
char a[2][MAXN];
short int next[2][MAXN];
short int poz[2][26];

inline void citire(int l, int &n, FILE *fin) {
    char ch = fgetc(fin);
    while (ch != '\n') {
        a[l][n++] = ch;
        ch = fgetc(fin);
    }
    for (int i = 0; i < 26; i++)
        poz[l][i] = n;
    for (int i = n - 1; i >= 0; i--) {
        next[l][i] = poz[l][a[l][i] - 'A'];
        poz[l][a[l][i] - 'A'] = i;
    }
}

inline void dinamica(int n, int m) {
    for (int i = 0; i <= n; i++)
        dp[i][m] = 0;
    for (int i = 0; i <= m; i++)
        dp[n][i] = 0;
    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
            if (a[0][i] == a[1][j]) dp[i][j] = 1 + dp[i + 1][j + 1];
            else dp[i][j] = std::max(dp[i + 1][j], dp[i][j + 1]);
}

int main() {
    FILE *fin = fopen("seif.in", "r"), *fout = fopen("seif.out", "w");

    int t;
    fscanf(fin, "%d", &t);

    for(; t; t--) {
        int k, n = 0, m = 0;
        fscanf(fin, "%d ", &k);

        citire(0, n, fin);
        citire(1, m, fin);

        dinamica(n, m);

        int x = 0, y = 0;
        bool f = 1;
        while (f) {
            f = 0;
            int ch = 'Z' - 'A';
            while (!f && ch >= 0) {
                while (poz[0][ch] < x) poz[0][ch] = next[0][poz[0][ch]];
                while (poz[1][ch] < y) poz[1][ch] = next[1][poz[1][ch]];
                if (poz[0][ch] < n && poz[1][ch] < m && dp[poz[0][ch]][poz[1][ch]] >= k) {
                    f = 1;
                    fputc(ch + 'A', fout);
                    k--;
                    x = poz[0][ch] + 1;
                    y = poz[1][ch] + 1;
                }
                ch--;
            }
            if (x >= n || y >= m)
                f = 0;
        }

        fputc('\n', fout);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}