Uva Homework solution

homework.cpp

/* Copyright 2017 Rafael Rendón Pablo <[email protected]> */
// region Template
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <map>
#include <cmath>

#include <cstring>
#include <cctype>
using namespace std;
typedef long long           int64;
typedef unsigned long long  uint64;
const int kMax      = 10005;
// endregion

int dp[kMax+1][3];

int f(int n, int k) {
    if (k == 0) {
        return (n == 0) ? 1 : 0;
    }
    if (n < 0) {
        return 0;
    }
    int& ans = dp[n][k];
    if (ans != -1) {
        return ans;
    }
    ans = 0;
    for (int s = 0; s <= n; s++) {
        ans += f(n - s, k - 1);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dp, -1, sizeof dp);
    map<int, int> m;
    for (int i = 0; i < kMax; i++) {
        int v = f(i, 3);
        // cout << i << ": " << v << endl;
        m[v] = i;
    }
    int T;
    cin >> T;
    while (T--) {
        int S;
        cin >> S;
        if (m.count(S) == 1) {
            cout << m[S] << "\n";
        } else {
            cout << "No solution\n";
        }
    }
    return EXIT_SUCCESS;
}