XLSL - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are three t-shirt sizes — S, L, and XL.
You have X, Y, Z t-shirts of each of these types, respectively.

There are A, B, C people who want t-shirts of sizes S, L, XL, respectively.
A t-shirt of one type can be converted to one t-shirt of a smaller type, if needed.
Find the maximum number of people who can receive a t-shirt of their preferred size.

EXPLANATION:

First, note that the small t-shirts are the most restrictive - they can’t be given to anyone other than people who need small t-shirts.
So, let’s give as many of the X small t-shirts to the A people who need them as we can.

Next, look at the large t-shirts.
These can be given to either people who want large, or people who want small (since it’s allowed to reduce size).
Note that it doesn’t really matter who we give it to as long as they want it, so just distribute the Y available t-shirts to as many people as possible.

Finally, there are Z extra-large t-shirts, which can be given to anyone. Again, distribute as many of them as possible till you’re done.

To implement this painlessly, a nice way is to store the counts of t-shirts and people in arrays and utilize loops.

Let a_1, a_2, a_3 be the counts of t-shirts of the three types, and b_1, b_2, b_3 be the counts of people who want each type.
Then, use the following algorithm:

  • Iterate i from 1 to 3.
    • Iterate j from 1 to i (since we can only make t-shirts smaller).
    • Once i and j are fixed, give \min(a_i, b_j) t-shirts of type i to people who want type j.
    • This means the answer increases by \min(a_i, b_j), while both a_i and b_j must reduce by \min(a_i, b_j).

Print the answer once the loop completes.
This results in a simple implementation without having to think much about casework at all.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    a, b, c, x, y, z = map(int, input().split())

    s = [a, b, c]
    t = [x, y, z]
    ans = 0
    for i in range(3):
        for j in range(i+1):
            take = min(s[i], t[j])
            ans += take
            s[i] -= take
            t[j] -= take
    print(ans)