Akinator

#include <bits/stdc++.h>

using namespace std;

#define llong __int128
#define Fraction pair<llong, llong>

const int MAX = 100;

int n, k;
llong sum;
vector<llong> a;
vector<vector<vector<pair<int, Fraction>>>> memo;
char buffer[MAX];

void print(llong num) {
    int idx = 0;
    while (num) {
        char c = '0' + (num % 10);
        buffer[idx++] = c;
        num /= 10;
    }

    if (!idx) cout << "0";
    else {
        for (int i = idx - 1; i >= 0; i--)
            cout << buffer[i];
    }
}

llong gcd(llong a, llong b) {
    if (!b) return a;
    return gcd(b, a % b);
}

Fraction irreductible(llong num, llong den) {
    llong g = gcd(num, den);
    return make_pair(num / g, den / g);
}

Fraction operator +(Fraction &a, Fraction &b) {
    llong num = a.first * b.second + a.second * b.first;
    llong den = a.second * b.second;
    return irreductible(num, den);
}

bool operator <(Fraction &a, Fraction &b) {
    return a.first * b.second < a.second * b.first;
}

pair<int, Fraction> average(int i, int j, int guesses = 0) {
    if (guesses > k) return make_pair(false, make_pair(0LL, 0LL));
    if (i == j) return make_pair(true, irreductible(a[i] * guesses, sum));

    auto [possible, ans] = memo[i][j][guesses];
    if (~possible) return make_pair(possible, ans);

    possible = false;
    ans = make_pair(LLONG_MAX, 1);

    for (int m = i; m < j; m++) {
        auto [p1, a1] = average(i, m, guesses + 1);
        auto [p2, a2] = average(m + 1, j, guesses + 1);

        if (p1 && p2) {
            possible = true;
            Fraction a = a1 + a2;
            if (a < ans) ans = a;
        }
    }

    return memo[i][j][guesses] = make_pair(possible, ans);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;

    sum = 0LL;
    a.resize(n);

    for (int i = 0; i < n; i++) {
        long long int num; cin >> num;
        a[i] = num;
        sum += num;
    }

    sort(a.rbegin(), a.rend());

    memo.assign(n + 5, vector<vector<pair<int, Fraction>>>(n + 5, vector<pair<int, Fraction>>(k + 5, make_pair(-1, make_pair(LLONG_MAX, 1)))));

    auto [possible, ans] = average(0, n - 1);
    if (!possible) cout << "No solution\n";
    else {
        print(ans.first);
        cout << "/";
        print(ans.second);
        cout << "\n";
    }
}