coin34.cpp

#include<iostream>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<unordered_map>

#define long long long
#define nln '\n'

const long COIN = 34;

using namespace std;

void sums(
    vector<long> &vsm,
    unordered_map<long, long> &cnt,
    const vector<long> &a,
    long bgn, long end, long sum, long qtt)
{
    if (bgn == end)
    {
        if (!cnt[sum])
            cnt[sum] = qtt, vsm.push_back(sum);
        else
            cnt[sum] = max(cnt[sum], qtt);
        return;
    }
    sums(vsm, cnt, a, bgn+1, end, sum+a[bgn], qtt+1);
    sums(vsm, cnt, a, bgn+1, end, sum, qtt);
}

long use(
    long val,
    const vector<long> &sm1,
    const vector<long> &sm2,
    unordered_map<long, long> co1,
    unordered_map<long, long> co2)
{
    long res = -1;
    for (const auto &i : sm1)
        if (binary_search(sm2.begin(), sm2.end(), val-i))
            res = max(res, co1[i]+co2[val-i]);
    return res;
}

int main()
{
    // initialization
    // make coins
    vector<long> a(COIN, 0);
    a[0] = 2; a[1] = 3; a[2] = 5;
    for (long i = 3; i < COIN; ++i)
        a[i] = a[i-1]+a[i-2]+a[i-3];
    // build sums
    vector<long> sm1, sm2;
    unordered_map<long, long> co1, co2;
    sums(sm1, co1, a, 0, COIN/2, 0, 0);
    sums(sm2, co2, a, COIN/2, COIN, 0, 0);
    sort(sm2.begin(), sm2.end());
    // Process
    //freopen("coin34.inp", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    long tsc;
    cin >> tsc;
    for (long i = 1; i <= tsc; ++i)
    {
        long x;
        cin >> x;
        cout << "Case #" << i << ": " << use(x, sm1, sm2, co1, co2) << nln;
    }
    return 0;
}