Cod sursa(job #2712277)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 25 februarie 2021 16:00:52
Problema Pavare2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pavare2.in");
ofstream fout("pavare2.out");

void add(int A[], int B[], int C[], bool type) {
    int i, t = 0;
    if(type) {
        for(int k = A[0]; k >= 0; --k)
            C[k] = A[k];
        for(i = 1; i <= C[0] || i <= B[0] || t; ++i, t /= 10)
            C[i] = (t += C[i] + B[i]) % 10;
        C[0] = i - 1;
    }
    else {
        for(i = 1; i <= A[0] || i <= B[0] || t; ++i, t /= 10)
            A[i] = (t += A[i] + B[i]) % 10;
        A[0] = i - 1;
    }
}

void sub(int A[], int B[]) {
    int t = 0;
    for(int i = 1; i <= A[0]; ++i) {
        A[i] -= ((i <= B[0]) ? B[i] : 0) + t;
        A[i] += (t = A[i] < 0) * 10;
    }
    for(; A[0] > 1 && !A[A[0]]; --A[0]);
}

void print(int A[]) {
    for(int i = A[0]; i > 0; --i)
        fout << A[i];
    fout << '\n';
}

bool Less(int A[], int B[]) {
    if(A[0] != B[0])
        return A[0] < B[0];
    int p = A[0];
    while(p > 0 && A[p] == B[p])
        --p;
    return p > 0 && A[p] < B[p];
}

const int NMAX = 1e2 + 2;
int N, A, B, dp[NMAX][NMAX][2][NMAX], K[NMAX], ans[NMAX];
string s;

int main() {
    fin >> N >> A >> B >> s;
    K[0] = s.size();
    int p = 0;
    for(int i = K[0]; i > 0; --i)
        K[i] = s[p++] - '0';
    for(int i = 0; i < NMAX; ++i)
        for(int j = 0; j < NMAX; ++j)
            for(int k = 0; k < 2; ++k)
                dp[i][j][k][0] = 1;
    dp[0][0][0][1] = dp[0][0][1][1] = 1;
    // dp[i][j][k] - numarul de moduri de a alege culorile primelor i placi
    //               astfel incat ultimele j sa aiba culoarea k
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= i && j <= A; ++j) {
            add(dp[i][j][0], dp[i - j][0][0], ans, false);
            add(dp[i][0][1], dp[i][j][0], ans, false);
        }
        for(int j = 1; j <= i && j <= B; ++j) {
            add(dp[i][j][1], dp[i - j][0][1], ans, false);
            add(dp[i][0][0], dp[i][j][1], ans, false);
        }
    }
    add(dp[N][0][0], dp[N][0][1], ans, true);
    print(ans);
    int rem = N;
    bool zero = true;
    while(rem) {
        if(zero) {
            if(Less(dp[rem][0][1], K))
                sub(K, dp[rem][0][1]);
            else {
                for(int i = min(rem, A); i > 0; --i)
                    if(Less(dp[rem][i][0], K))
                        sub(K, dp[rem][i][0]);
                    else {
                        for(int j = 0; j < i; ++j)
                            fout << '0';
                        rem -= i;
                        break;
                    }
            }
        }
        else {
            if(Less(dp[rem][0][0], K))
                sub(K, dp[rem][0][0]);
            else {
                for(int i = 1; i <= min(B, rem); ++i)
                    if(Less(dp[rem][i][1], K))
                        sub(K, dp[rem][i][1]);
                    else {
                        for(int j = 0; j < i; ++j)
                            fout << '1';
                        rem -= i;
                        break;
                    }
            }
        }
        zero ^= 1;
    }
}