Cod sursa(job #2205913)

Utilizator jack92657Jacky boy jack92657 Data 20 mai 2018 16:25:10
Problema Pavare2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

typedef long double ll;
int n, a[2];
ll pd[2][105][105];

int main()
{
    ifstream fin ("pavare2.in");
    ofstream fout ("pavare2.out");
    fin >> n >> a[0] >> a[1];
    for (int i = 1; i <= a[0]; ++i)
        pd[0][i][0] = 1;
    for (int i = 1; i <= a[1]; ++i)
        pd[1][i][0] = 1;
    for (int i = 1; i < n; ++i)
        for (int t = 0; t < 2; ++t)
            for (int j = 1; j <= a[t] && j+i <= n; ++j)
                for (int k = 1; k <= a[1-t] && k <= i; ++k)
                    pd[t][j][i] += pd[1-t][k][i-k];
    ll ans = 0, ans2;
    for (int i = 1; i <= a[0]; ++i)
        ans += pd[0][i][n-i];
    ans2 = ans;
    for (int i = 1; i <= a[1]; ++i)
        ans += pd[1][i][n-i];
    fout << fixed << setprecision(0) << ans << "\n";
    ll k = 0;
    char q;
    while(fin >> q){
        q -= '0';
        k = k*10+q;
    }
    int p = 1, type;
    if(ans2 < k){
        k -= ans2;
        type = 1;
    }else type = 0;
    while(p <= n){
        int rem = n-p+1;
        if(type == 0){
            int last = a[0];
            ll all = 0;
            for (int i = a[0]; i >= 1; --i){
                all += pd[0][i][rem-i];
                if(all < k)
                    last = i;
                else break;
            }
            k -= all-pd[0][last][rem-last];
            for (int i = 1; i <= last; ++i){
                fout << 0;
                ++p;
                if(p == n+1)
                    break;
            }
        }else{
            int first = 1;
            ll all = 0;
            for (int i = 1; i <= a[1]; ++i){
                all += pd[1][i][rem-i];
                if(pd[1][i][rem-i] >= k){
                    first = i;
                    break;
                }
            }
            k -= all-pd[1][first][rem-first];
            for (int i = 1; i <= first; ++i){
                fout << 1;
                ++p;
                if(p == n+1)
                    break;
            }
        }
        type = 1-type;
    }
    return 0;
}