Submission #57921

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

typedef long long Long;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    Long s = 0, m = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        s += a[i];
        m += b[i];
    }

    vector<int> q(n), r(n);
    while (true) {
        Long rest = m;
        for (int i = 0; i < n; i++) {
            q[i] = (m * a[i]) / s;
            r[i] = (m * a[i]) % s;
            if (q[i] + 1 < b[i]) goto fail;
            rest -= q[i];
        }
        for (int i = 0; i < n; i++) {
            if (q[i] >= b[i]) continue;
            int k = 0;
            for (int j = 0; j < n; j++) {
                if (r[i] < r[j] || (r[i] == r[j] && i > j)) ++k;
            }
            if (k >= rest) goto fail;
        }
        break; // good
    fail:
        ++m;
    }

    cout << m << endl;
    return 0;
}

Submission Info

Judge Result