F - Tom & Jerry Space Adventure.cpp

// Language: C++
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#ifdef LOCAL
#define dmp(x) cerr << _LINE_ << " " << #x << " " << x << endl
#else
#define dmp(x) void(0)
#endif

template <class t, class u>
void chmax(t &a, u b)
{
    if (a < b)
        a = b;
}
template <class t, class u>
void chmin(t &a, u b)
{
    if (b < a)
        a = b;
}

template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;

using pi = pair<int, int>;
using vi = vc<int>;

template <class t, class u>
ostream &operator<<(ostream &os, const pair<t, u> &p)
{
    return os << "{" << p.a << "," << p.b << "}";
}

template <class t>
ostream &operator<<(ostream &os, const vc<t> &v)
{
    os << "{";
    for (auto e : v)
        os << e << ",";
    return os << "}";
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    int n;
    cin >> n;
    int as = 0;
    vc<pi> ab;
    rep(_, n)
    {
        int a, b;
        cin >> a >> b;
        ab.eb(max(a, b), b);
        as += a;
    }
    sort(all(ab), greater<pi>());

    int s = 0, k = 0;
    while (1)
    {
        s += ab[k++].a;
        if (s >= as)
            break;
    }

    int num = 1, den = 1;
    auto upd = [&](int x, int y)
    {
        if (num * y > x * den)
            tie(num, den) = tie(x, y);
    };
    rep(i, n)
    {
        int w = as - (s - ab[min(i, k - 1)].a);
        if (w <= ab[i].b)
            upd(w, ab[i].b);
    }

    num = den - num + den * (n - k);
    den *= n;
    int g = gcd(num, den);
    cout << num / g << " " << den / g << endl;
}