Cod sursa(job #2630844)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 27 iunie 2020 14:45:05
Problema Pavare2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <bits/stdc++.h>
#define maxn 1005

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

std::vector <int> dp[2][maxn];

void add (std::vector <int> &a, std::vector <int> &b){
    int i, j, val=0;
    for (i=0, j=0; i<a.size() or j<b.size()or val; i++, j++){
        if (i < a.size()) val += a[i];
        if (j < b.size()) val += b[j];

        if (i < a.size())
            a[i] = val % 10;
        else a.push_back (val % 10);
        val /= 10;
    }
}

bool compare (std::vector <int> &a, std::vector <int> &b){
    if (a.size() < b.size()) return 0;
    if (a.size() > b.size()) return 1;
    for (int i=a.size()-1; i>=0; i--){
        if (a[i] > b[i])
            return 1;
        if (a[i] < b[i])
            return 0;
    }
    return 0;
}

void reduce (std::vector <int> &a, std::vector <int> &b){
    int last = 0;
    for (int i=0; i<a.size(); i++){
        if (i < b.size()) last -= b[i];
        last += a[i];
        if (last < 0){
            a[i] = last + 10;
            last = -1;
        }
        else{
            a[i] = last;
            last = 0;
        }
    }
    if (a[a.size()-1] == 0)
        a.pop_back();
}

void print (std::vector <int> &nr){
    for (int i=nr.size()-1; i>=0; i--)
        fout << nr[i];
    fout << '\n';
}

int main()
{
    int n, maxWhite, maxBlack, i, j, crt=0, last=-1;
    std::vector <int> K;
    std::string s;
    fin >> n >> maxWhite >> maxBlack;
    dp[0][0].push_back(1);
    dp[1][0].push_back(1);
    for (i=1; i<=n; i++){
        for (j=1; j<=maxWhite and j<=i; j++)
            add (dp[0][i], dp[1][i-j]);
           // dp[0][i] += dp[1][i-j];
        for (j=1; j<=maxBlack and j<=i; j++)
            add (dp[1][i], dp[0][i-j]);
           // dp[1][i] += dp[0][i-j];
    }
    std::vector <int> ans;
    add (ans, dp[0][n]);
    add (ans, dp[1][n]);
    print(ans);
    //fout << dp[0][n] + dp[1][n] << '\n';

    fin >> s;
    for (i=s.size()-1; i>=0; i--)
        K.push_back (s[i]-'0');
        //print(K);
    while (crt < n){
        if (last != 0)
        for (j=std::min (maxWhite, n-crt); j>=1; j--){
            if (compare (K, dp[1][n-crt-j]) == 0){
            //if (K <= dp[1][n-crt-j]){
                crt += j;
                while (j--)
                    fout << 0;
                last = 0;
                break;
            }
            reduce (K, dp[1][n-crt-j]);
            //print (K);
            //K -= dp[1][n-crt-j];
        }

        if (last != 1)
        for (j=1; j<=std::min (maxBlack, n-crt); j++){
            if (compare (K, dp[0][n-crt-j]) == 0){
            //if (K <= dp[0][n-crt-j]){
                crt += j;
                while (j--)
                    fout << 1;
                last = 1;
                break;
            }
            reduce (K, dp[0][n-crt-j]);
           // print (K);
            //K -= dp[0][n-crt-j];
        }
    }
    return 0;
}