Cod sursa(job #2071709)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 20 noiembrie 2017 22:01:29
Problema Lampa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <string>

FILE *fin = fopen("lampa.in", "r"), *fout = fopen("lampa.out", "w");

#define MAXM 3027197
#define MAXN 25

char t[MAXM + 10], s1[5000], s2[5000];
int n, m, nb, a, b;
std::string s[MAXN + 1];

inline bool bun(int na) {
    nb = (m - na * a) / b;
    if (nb <= 0 || na * a + nb * b != m)
        return 0;

    int p = 0;
    if (n % 2) {
        for (int i = 0; i < na; i++)
            s1[i] = t[i];
        for (int i = 0; i < nb; i++)
            s2[i] = t[i + na];
    } else {
        for (int i = 0; i < nb; i++)
            s2[i] = t[i];
        for (int i = 0; i < na; i++)
            s1[i] = t[i + nb];
    }
    for (auto &x : s[n]) {
        if (x == 'a') {
            for (int i = 0; i < na; i++)
                if (s1[i] != t[p]) return 0;
                else p++;
        } else {
            for (int i = 0; i < nb; i++)
                if (s2[i] != t[p]) return 0;
                else p++;
        }
    }
    return 1;
}

int main() {
    fscanf(fin, "%d%d ", &n, &m);

    fgets(t, m + 5, fin);

    s[1] = "a";
    s[2] = "b";
    for (int i = 3; i <= n; i++)
        s[i] = s[i - 2] + s[i - 1];

    for (auto &i : s[n])
        if (i == 'a') a++;
        else b++;

    int lim = (m - b) / a, na = 1;
    while (na <= lim && !bun(na))
        na++;

    if (na > lim) fprintf(fout, "0\n");
    else if (n % 2) {
        for (int i = 0; i < na; i++)
            fputc(t[i], fout);
        fputc('\n', fout);
        for (int i = na; i < na + nb; i++)
            fputc(t[i], fout);
        fputc('\n', fout);
    } else {
        for (int i = nb; i < na + nb; i++)
            fputc(t[i], fout);
        fputc('\n', fout);
        for (int i = 0; i < nb; i++)
            fputc(t[i], fout);
        fputc('\n', fout);
    }

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