Problem A

This is a very easy problem. Got it right at my first submission. My very simple solution was based on these two observations:

  1. we can make a soup with V litres
  2. There exist an i such that b[i] (the b here is the b in the problem statement. Confuse? Read the problem statement again :D) litres of ingredient i was mixed

The rest should be obvious. Iterate for all possible i, fix the amount of i which was mixed in the soup with b[i] and calculate the other amount according to the proportion. If it is possible (the amount of ingredient j used in the soup is less than or equal to b[j] for all j), than the total amount of ingredient used according to this rule is one of the candidate solution. Try to maximize it! If the maximum is greater than V, it means that we can make a V-litres soup. And since we cannot make more than V litre soup, output V.

Here is my code:

int n, V;
int a[1000], b[1000];

int main () {
    scanf ("%d%d", &n, &V);

    REP (i, n) scanf ("%d", &a[i]);
    REP (i, n) scanf ("%d", &b[i]);

    double ret = 0;

    REP (i, n) {
        LL ctr = 0;
        bool test = true;
        REP (j, n) {
            if (a[j] * b[i] > b[j] * a[i]) {
                test = false;
                break;
            } else {
                ctr += a[j] * b[i];
            }
        }
        if (!test) continue;
        ret = max (ret, 1. * ctr / a[i]);
    }

    ret = min (ret, 1. * V);

    printf ("%.6lf\n", ret);

    return 0;
}
Advertisements